Математика: темы
Дискретная математика
Формулы и правила по теме «Дискретная математика».
25 формул
Таблица формул
| Формула | Запись | Тема | Для чего нужна |
|---|---|---|---|
| Правило суммы в комбинаторике | $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$ | Дискретная математика | Формула описывает прием «подсчет пар вершин» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета. |
| Перестановки с повторениями: одинаковые элементы | $P=\frac{n!}{n_1!n_2!\cdots n_r!},\qquad n_1+\cdots+n_r=n$ | Дискретная математика | Число различных упорядоченных записей из заданного набора элементов, среди которых есть одинаковые. Формула делит все перестановки на перестановки внутри каждой группы неразличимых элементов. |
| Сочетания с повторениями: метод звёзд и перегородок | $\overline C_n^k=\binom{n+k-1}{k}=\frac{(n+k-1)!}{k!(n-1)!}$ | Дискретная математика | Формула считает наборы из k элементов n видов, когда один вид разрешено выбирать несколько раз, а порядок выбора не важен. Эквивалентная задача — распределить k одинаковых предметов по n различимым ящикам. |
| Беспорядки: перестановки без неподвижных точек | $D_n=n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}$ | Дискретная математика | Беспорядок — перестановка, в которой ни один элемент не остаётся на своём первоначальном месте. Формула включений и исключений считает такие перестановки и помогает находить вероятность полного несовпадения. |
| Числа Каталана: правильные скобочные последовательности | $C_n=\frac{1}{n+1}\binom{2n}{n}$ | Дискретная математика | Число Каталана Cₙ считает правильные последовательности из n пар скобок одного вида. В каждом начальном фрагменте открывающих скобок должно быть не меньше закрывающих, а в полной записи их количества равны. |
| Числа Стирлинга второго рода: разбиение на группы | $S(n,k)=kS(n-1,k)+S(n-1,k-1)$ | Дискретная математика | Число Стирлинга второго рода S(n,k) показывает, сколькими способами можно разбить n различных элементов на k непустых неименованных групп. Рекурсия отделяет добавление элемента в старую группу от создания новой. |
| Числа Белла: все разбиения множества на группы | $B_n=\sum_{k=0}^{n}S(n,k),\qquad B_0=1$ | Дискретная математика | Число Белла считает все способы разделить различимые элементы на непустые непересекающиеся группы. Число групп заранее не задано, их порядок и порядок элементов внутри группы не учитываются. |
| Числа Стирлинга первого рода: циклы перестановки | $c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$ | Дискретная математика | Беззнаковые числа Стирлинга первого рода считают перестановки n различных элементов, состоящие ровно из k циклов. Рекурсия отделяет новый одноэлементный цикл от вставки элемента в существующий цикл. |
| Круговые перестановки: рассадка за круглым столом | $P_{\mathrm{circle}}(n)=\frac{n!}{n}=(n-1)!,\qquad n\ge1$ | Дискретная математика | Число круговых перестановок n различных объектов равно (n−1)!, если повороты всей расстановки считаются одинаковыми. Зеркальное отражение при этом обычно даёт другой порядок соседей. |
| Число сюръекций: распределение без пустых ящиков | $N(n,k)=k!S(n,k)=\sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n$ | Дискретная математика | Сюръективное отображение отправляет n различимых объектов в k различимых ящиков так, чтобы каждый ящик был занят. Формула считает такие распределения через числа Стирлинга или включения и исключения. |
| Формула Кэли: число деревьев с помеченными вершинами | $T_n=n^{n-2},\qquad n\ge2$ | Дискретная математика | Формула Кэли считает неориентированные деревья на заданных n различных вершинах: связные графы без циклов. Метки вершин сохраняются, а расположение рисунка на плоскости не создаёт новых деревьев. |
| Поиск в глубину: дерево обхода и времена входа и выхода | $u\text{ — предок }v\iff t_{in}(u)<t_{in}(v)<t_{out}(v)<t_{out}(u),\quad u\ne v$ | Алгоритмы и анализ данных | Поиск в глубину, или DFS, полностью исследует одну ветвь графа перед возвратом к следующей. Времена входа и выхода образуют вложенные интервалы и позволяют проверять родство в дереве обхода. |
| Топологическая сортировка Кана по входящим степеням | $d_{in}(v)\leftarrow d_{in}(v)-1\quad\text{при удалении дуги }u\to v;\qquad |L|=|V|\iff G\text{ ацикличен}$ | Алгоритмы и анализ данных | Алгоритм Кана упорядочивает вершины ориентированного графа, последовательно выбирая вершину без входящих дуг. Если вывести все вершины не удалось, оставшаяся часть содержит ориентированный цикл. |
| Сильные компоненты: два обхода алгоритма Косарайю | $u\sim v\iff(u\leadsto v)\land(v\leadsto u),\qquad T=O(|V|+|E|)$ | Алгоритмы и анализ данных | Сильная компонента ориентированного графа объединяет вершины, достижимые друг из друга в обоих направлениях. Алгоритм Косарайю находит такие группы двумя обходами в глубину с разворотом всех дуг. |
| Мосты графа: критерий через времена входа и low | $(v,u)\text{ — мост}\iff low(u)>t_{in}(v),\quad u\text{ — ребёнок }v\text{ в DFS}$ | Алгоритмы и анализ данных | Мост — ребро неориентированного графа, удаление которого увеличивает число компонент связности. DFS обнаруживает его, если поддерево ребёнка не имеет обходного ребра к родителю или его предкам. |
| Точки сочленения: критерий low и отдельное правило корня | $v\ne root:\quad v\text{ — точка сочленения}\iff\exists u\text{ — ребёнок}:low(u)\ge t_{in}(v)$ | Алгоритмы и анализ данных | Точка сочленения — вершина, удаление которой вместе с инцидентными рёбрами увеличивает число компонент связности. Для некорневой вершины DFS использует нестрогое сравнение low ребёнка с временем входа. |