Kombinatorics
Конспект по книге Комбинаторика Виленкина
Основы
Правило суммы
\[m+n\]Если некоторый объект A можно выбрать m способами, а другой объект B можно выбрать n способами, то выбор "Либо A, либо B" можно осуществить m+n способами
Если способы начинают пересекаться k раз, то получаем m+n-k способов
Правило произведения
\[m*n\]Если объект A можно выбрать m способами и если после каждого такого выбора объект B можно выбрать n способами, то выбор пары (A, B) в указанном порядке можно осуществить mn способами
Формула включений и исключений
$N(a_ia_j…a_k)$ - количество предметов обладающих свойствами $a_i$,$a_j$,…,$a_k$( и возможно ещё другими свойствами)
$a’_j$ - не обладает свойством $a_j$
\[N(a'_1a'_2...a'_n) = N - N(a_1)- N(a_2)- ... - N(a_n) + \\ N(a_1a_2) + N(a_1a_3) + ... + N(a_1a_n) + ... + N(a_{n-1}a_n) - \\ N(a_1a_2a_3) - ... - N(a_{n-2}a_{n-2}a_n) + ... + (-1)^nN(a_1a_2...a_n)\]Формула доказывается по индукции.
Размещения, перестановки, сочетания
k-расстановки(размещения) – набор предметов из k элементов
Размещения с повторениями
n видов, по k предметов
\[\overline{A_n^k}=n^k\]Размещения без повторений
n различных предметов, сколько можно составить к-расстановок
\[A_n^k=n(n-1)...(n-k+1)\]или
\[A_n^k={ {n!}\over{(n-k)!} }\]Перестановки с повторениями
Имеются предметы k различных типов. Сколько перестановок можно сделать из $n_1$ элементов первого типа, $n_2$ элементов второго типа, …, $n_k$ элементов k-го типа
\[P(n_1,n_2,...,n_k) = { {n!}\over{n_1! n_2! ... n_k!} }\]Сочетания
k-сочетания из n элементов называют всевозможные k-расстановки, составленные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов
\[k!C^k_n = A^k_n\] \[\implies\] \[C^k_n = { {A^k_n}\over{k!} } = { {n!}\over{(n-k)!k!} } = P(k, n-k)\]Сочетания с повторениями
Имеются предметы n различных типов. Сколько k-комбинаций можно сделать из них, если не принимать во внимание порядок элементов в комбинации
\[\overline{C^k_n} = P(k,n-1) = { {(k+n-1)!}\over{k!(n-1)!} } = C^k_{n+k-1}\]Свойства сочетаний
1)\(C^k_n = C^{n-k}_n\)
2)\(C^k_n = C^{k-1}_{n-1} + C^{k}_{n-1}\)
3) \(C^0_n + C^1_n + C^2_n + ... + C^n_n = 2^n\)
Знакомеременные суммы сочетаний
1) \(C^0_n - C^1_n + C^2_n + ... + (-1)^nC^n_n = 0\)
И другие …
Задачи с ограничениями
Общая задача о смещении
Найти число $D_n$ перестановок из n элементов, при которых ни один элемент не остаётся в первоначальном положении
\[D_n = P_n - C^1_n P_{n-1} + C^2_n P_{n-2} - ... + (-1)^nC^n_n = n! [1 - { {1}\over{1!} } + { {1}\over{2!} } - ... + { {(-1)^n}\over{n!} } ]\]#matematics #combinatorics