Математика: темы
Дискретная математика
Формулы и правила по теме «Дискретная математика».
10 формул
Таблица формул
| Формула | Запись | Тема | Для чего нужна |
|---|---|---|---|
| Правило суммы в комбинаторике | $N=m_1+m_2+\cdots+m_k$ | Графы, логика | Формула описывает прием «сложение несовместных случаев» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета. |
| Правило произведения в комбинаторике | $N=m_1m_2\cdots m_k$ | Графы, логика | Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета. |
| Число перестановок без повторений | $P_n=n!$ | Графы, логика | Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета. |
| Число размещений без повторений | $A_n^k=\frac{n!}{(n-k)!}$ | Графы, логика | Формула описывает прием «упорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета. |
| Число сочетаний без повторений | $C_n^k=\binom nk=\frac{n!}{k!(n-k)!}$ | Графы, логика | Формула описывает прием «неупорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета. |
| Бином Ньютона для конечной степени | $(a+b)^n=\sum_{k=0}^n\binom nk a^{n-k}b^k$ | Графы, логика | Формула описывает прием «биномиальное разложение» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета. |
| Формула включений и исключений для двух множеств | $|A\cup B|=|A|+|B|-|A\cap B|$ | Графы, логика | Формула включений и исключений для двух множеств считает размер объединения A и B: складывает мощности множеств и один раз вычитает их пересечение. Она нужна, когда объект может иметь оба признака сразу, поэтому простая сумма дает двойной счет. |
| Формула включений и исключений для трех множеств | $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$ | Графы, логика | Формула включений и исключений для трех множеств считает элементы, попавшие хотя бы в одно из A, B или C. Она складывает три мощности, вычитает попарные пересечения и возвращает тройное пересечение, чтобы каждый объект был учтен ровно один раз. |
| Рекуррентная формула чисел Фибоначчи | $F_0=0,\quad F_1=1,\quad F_n=F_{n-1}+F_{n-2}$ | Графы, логика | Формула описывает прием «рекуррентное сложение» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета. |
| Число ребер полного графа | $E(K_n)=\binom n2=\frac{n(n-1)}2$ | Графы, логика | Формула описывает прием «подсчет пар вершин» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета. |