Таблица формулы комбинаторики.
Правило умножения.
Если первый элемент A можно выбрать $n$ способами, а второй элемент B — $m$ способами, то оба элемент (A и B) в указанном порядке можно выбрать $n \cdot m$ способами.
Правило сложения.
Если первый элемент A можно выбрать $n$ способами, а второй элемент B — $m$ способами, причём первые и вторые способы не пересекаются, то любой из элементов (A или B) можно выбрать $n + m$ способами.
Основные формулы комбинаторики.
$n$ — число элементов данного множества. $k$ — число элементов составляемого подмножества. По определению $0! = 1$.
Размещения Allocations
$$ A^k_n = \dfrac{n!}{(n-k)!} $$Упорядоченные подмножества. Отличаются или составом, или порядком элементов.
Перестановки Permutations
$$ P_n = n! $$Отличаются только порядком следования элементов.
Сочетания Combinations
$$ C_n^k = \dfrac{n!}{k! \cdot (n-k)!} $$Отличаются только составом элементов. (Порядок не важен.)
Схема выбора с возвращением.
Размещения с повторениями
$$ \overline{A}^k_n = n^k $$Упорядоченные подмножества. Элементы могут повторяться.
Сочетания с повторениями
$$ \overline{C}^{k}_{n} = \dfrac{(n+k-1)!}{k! (n-1)!} $$Порядок не важен. Элементы могут повторяться.
Перестановки с повторениями
$$ P_n(n_1,n_2,\dots,n_k) = \dfrac{n!}{n_1! \cdot n_2! \cdot {\dots} \cdot n_k!} $$Число разбиений множества.
Сводка формул комбинаторики (файл).
Здесь можно скачать таблицу формул комбинаторики как файл PDF для печати на A4.
