Комбинаторикой или комбинаторным анализом называется раздел математики, посвященный решению задач выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами.

Пусть имеется множество, состоящее из $ n_{} $ элементов. Упорядочим их определенным образом и каждое такое упорядочение назовем перестановкой этих элементов.

Пример. Рассмотрим буквы а д к л о . Перестановкой этих букв является любое пятибуквенное слово, состоящее исключительно только из этих букв и к тому же без их повторений. Например, перестановками будут слова лодка, оклад, дклоа и т.п. (неважно осмысленны они или нет).

Пример. Перестановка в колоде игральных карт ♦, ♣, ♥, ♠ получается их тасованием.

Задача. Сколько всего существует перестановок $ n_{} $ элементов?

Для ответа на этот вопрос сформируем сначала гипотезу. Для $ n_{}=1 $ существует только одна перестановка. Для $ n_{}=2 $ имеем две: а, д $ \rightarrow $ а д и д а . Для $ n_{}=3 $ получаем уже шесть:

к, л, о $ \rightarrow $ к л о , к о л , л к о , л о к , о к л , о л к .

Теорема 1. Число всех перестановок из $ n_{} $ элементов равно $ n_{}! $.

Доказательство проводится методом математической индукции. Для $ n_{}=1 $ результат, очевидно, верен. Предположим, что результат верен для перестановок $ k_{} $ элементов. Рассмотрим все перестановки $ (k+1) $-го элемента, для простоты рассмотрев случай чисел $ \{1,\dots,k,k+1\} $. Будем обозначать перестановку этих чисел $ (\alpha_1,\dots,\alpha_k, \alpha_{k+1}) $. Это множество перестановок разобьем на подмножества. К первому подмножеству отнесем перестановки, у которых число $ k+1 $ оказывается на первом месте, т.е. перестановки вида $ (k+1,\alpha_1,\dots,\alpha_k) $. Ко второму подмножеству отнесем перестановки вида $ (\beta_1,k+1,\dots,\beta_k) $, и т.д., к $ (k+1) $-му — перестановки вида $ (\omega_1,\dots,\omega_k,k+1) $. Если обратиться к примеру с буквами, то можно сказать, что мы производим упорядочивание множества всевозможных слов, расставляя их по алфавиту:

$ \big\{ $ а д к л о , а д к о л , а д л к о , а д л о к , а д о л к , … $ \big\} $

$ \big\{ $ д а к л о , д а л к о , д а л о к , д а о к л , д а о л к , … $ \big\} $

…

Все эти подмножества не пересекаются, каждое из них содержит по $ k! $ элементов. Действительно, каждая перестановка $ (k+1,\alpha_1,\dots,\alpha_k) $ порождается перестановкой $ k_{} $ элементов $ (\alpha_1,\dots,\alpha_k) $: к каждой такой перестановке мы «приставляем» слева число $ k+1 $. Аналогичное рассуждение справедливо и для других подмножеств. По индукционному предположению, каждое из подмножеств содержит $ k! $ элементов. Следовательно, их объединение — это множество из $ (k+1)\times k!=(k+1)! $ элементов. ♦

Вспомогательный материал к пункту ☞ ОПРЕДЕЛЕНИЕ ОПРЕДЕЛИТЕЛЯ

Упорядоченная пара $ (a,b) $ различных натуральных чисел образует инверсию (или нарушение порядка) если $ a>b $. Можно ввести счетчик инверсий: $$\operatorname{inv}(a,b)= \left\{ \begin{array}{cc} 1 & \iff a>b ; \\ 0 & \iff a<b \end{array} \right. $$ и с его помощью распространить определение на перестановку $ (\alpha_1,\alpha_2,\dots,\alpha_n) $ чисел $ \{1,2.\dots,n \} $: $$ \operatorname{inv}(\alpha_1,\alpha_2,\dots,\alpha_n) = \sum_{1\le j <k \le n} \operatorname{inv}(\alpha_j,\alpha_k) \, . $$

Показать, что

$$ \max \operatorname{inv}(\alpha_1,\alpha_2,\dots,\alpha_n)=\frac{n(n-1)}{2} \, .$$

Показать, что

$$ \operatorname{inv}(\alpha_1,\dots,\alpha_k,\beta_1,\dots,\beta_{\ell})= $$ $$ =\operatorname{inv}(\alpha_1,\dots,\alpha_k)+\operatorname{inv}(\beta_1,\dots,\beta_{\ell})+ \sum_{\scriptstyle 1\le i \le k \atop \scriptstyle 1\le j \le \ell} \operatorname{inv}(\alpha_i,\beta_j) \, . $$

Перестановки с четным числом инверсий называются четными, с нечетным — нечетными.

Рассмотрим две перестановки $$\Theta=(a_1,\dots,a_K,{\color{Red} \alpha },b_1,\dots,b_{L}, {\color{DarkGreen} \beta },c_1,\dots,c_M)$$ $$\Xi=(a_1,\dots,a_K,{\color{DarkGreen} \beta },b_1,\dots,b_{L},{\color{Red} \alpha },c_1,\dots,c_M)$$ Говорят, что перестановка $ \Xi $ получена из перестановки $ \Theta $ в результате транспозиции.

Теорема 2. Любая транспозиция меняет четность перестановки: $$ \operatorname{inv} \Theta - \operatorname{inv} \Xi =\mbox{нечетное число} \, . $$

Доказательство. I. Предположим сначала, что $ L=0 $, т.е. производится транспозиция соседних элементов. $$ \operatorname{inv} \Theta = \operatorname{inv} (a_1,\dots,a_K,{\color{Red} \alpha },{\color{DarkGreen} \beta },c_1,\dots,c_M)= $$ В соответствии с определением инверсии, имеем $$ = \sum_{1\le i <j \le K}\operatorname{inv}(a_i,a_j)+ \sum_{1\le i \le K}\operatorname{inv}(a_i,{\color{Red} \alpha })+ \sum_{1\le i \le K}\operatorname{inv}(a_i,{\color{DarkGreen} \beta })+ $$ $$ +\sum_{\scriptstyle 1\le i \le K \atop \scriptstyle 1\le \ell \le M} \operatorname{inv}(a_i,c_{\ell})+\operatorname{inv}({\color{Red} \alpha },{\color{DarkGreen} \beta })+ $$ $$ +\sum_{1\le \ell \le M}\operatorname{inv}({\color{Red} \alpha },c_{\ell}) +\sum_{1\le \ell \le M}\operatorname{inv}(\beta,c_{\ell})+\sum_{1\le i <j \le M}\operatorname{inv}(c_i,c_j) \, . $$ Разложение для $ \operatorname{inv} \Xi $ отличается от этого только пятым слагаемым, которое меняется на $ \operatorname{inv} ({\color{DarkGreen} \beta },{\color{Red} \alpha }) $. Поэтому $$\operatorname{inv} \Theta - \operatorname{inv} \Xi =\operatorname{inv} ({\color{Red} \alpha },{\color{DarkGreen} \beta })- \operatorname{inv} ({\color{DarkGreen} \beta },{\color{Red} \alpha })= \pm 1. $$

II. Покажем, что сумма произвольного нечетного количества чисел, каждое из которых равно $ +1 $ или $ -1 $ есть число нечетное. Пусть среди заданных чисел $ \omega_1,\dots,\omega_{2N+1} $ имеется $ p $, равных $ 1 $, и $ q $ , равных $ -1 $. Тогда $$2N+1=p+q \, , $$ и $$ \omega_1+\dots+\omega_{2N+1}=p-q =2N+1-2q=2(N-q)+1 \, . $$

III. Покажем теперь справедливость утверждения теоремы для любого $ L \in \mathbb N $ . $$ \operatorname{inv} \Theta = \operatorname{inv} (a_1,\dots,a_K,{\color{Red} \alpha }, b_1,\dots,b_{L},{\bf \beta},c_1,\dots,c_M)= $$ $$ =\operatorname{inv} (a_1,\dots,a_K,b_1,{\color{Red} \alpha }, \dots,b_{L},{\color{DarkGreen} \beta },c_1,\dots,c_M) +\omega_1=\dots= $$ $$ =\operatorname{inv} (a_1,\dots,a_K,b_1, \dots,b_{L},{\color{Red} \alpha },{\color{DarkGreen} \beta },c_1,\dots,c_M) +\omega_1+\dots+\omega_L= $$ $$ =\operatorname{inv} (a_1,\dots,a_K,b_1, \dots,b_{L},{\color{DarkGreen} \beta },{\color{Red} \alpha },c_1,\dots,c_M) +\omega_1+\dots+\omega_L+\omega_{L+1}= $$ $$ =\operatorname{inv} (a_1,\dots,a_K,b_1, \dots,{\color{DarkGreen} \beta },b_{L},{\color{Red} \alpha },c_1,\dots,c_M) +\omega_1+\dots+\omega_L+\omega_{L+1}+\omega_{L+2}=\dots= $$ $$ =\operatorname{inv} (a_1,\dots,a_K,{\color{DarkGreen} \beta },b_1, \dots,b_{L},{\color{Red} \alpha },c_1,\dots,c_M) +\omega_1+\dots+\omega_{2L+1}= $$ $$ = \operatorname{inv} \Xi +\mbox{ нечетное число} \, . $$ ♦

Теорема 3. Число четных перестановок из $ n>1 $ элементов равно числу нечетных (и равно $ n!/2 $).

Доказательство. Действительно, упорядочим все множество перестановок таким образом, чтобы каждая следующая получалась из предшествующей с помощью одной транспозиции. Возможность такого упорядочения доказывается индукцией по $ n $. Для $ n=2 $ это тривиально: $ (1,2) $ и $ (2,1) $. Предположим, что утверждение верно для перестановок из $ (n-1) $-го элемента, т.е. их можно расположить в требуемом порядке.

Все множество перестановок из $ n $ элементов разобьем на подмножества по тем же правилам, что и в доказательстве теоремы $ 1 $. На основании индукционного предположения перестановки из первого подмножества $ (\alpha_1,\dots,\alpha_{n-1},n) $ можно упорядочить нужным нам образом. В получившейся последовательности перестановок возьмем последнюю и переставим местами $ n $ и $ n-1 $; в результате получим перестановку из второго подмножества $ (\beta_1,\dots,\beta_{n-1},n-1) $. По индукционному предположению и эти перестановки можно упорядочить так, как требуется. В последней получившейся переставим местами $ n-1 $ и $ n-2 $, получим перестановку из третьего класса $ (\gamma_1,\dots,\gamma_{n-1},n-2) $ и т.д.

Таким способом можно упорядочить все $ n! $ перестановок. По теореме $ 2 $ соседние перестановки должны иметь разные четности. ♦

В некоторых задачах комбинаторики порядок, в котором производится выбор элементов, не имеет значения. Например, из множества, содержащего $ n_{} $ элементов, требуется выбрать подмножество, содержащее $ m_{} $ ($ m\le n_{} $) элементов. Хотя мы и записываем такие подмножества, каким-то образом расставляя их элементы, но порядок их следования несуществен. Каждую такую выборку назовем сочетанием из $ \mathbf n $ элементов по $ \mathbf m $ элементов.

Задача. Сколько всего существует таких сочетаний?

Пример. Всего существует $ 10_{} $ сочетаний из элементов а д к л о , взятых по $ 3_{} $:

а д к , а д л , а д о , а к л , а к о , а л о , д к л , д к о , д л о , к л о .

Теорема 4. Число сочетаний из $ n_{} $ элементов по $ m_{} $ элементов равно $$ \frac{n!}{m!(n-m)!} \ . $$

Доказательство. Обозначим пока неизвестное нам число сочетаний через $ x_{} $. Рассмотрим множество всех перестановок из $ n_{} $ элементов. Каждую такую перестановку $ \left(\alpha_1,\dots, \alpha_n \right) $ можно представить в виде упорядоченной пары двух перестановок — первых $ m_{} $ элементов и последних $ n-m_{} $ элементов: $ \left(\alpha_1,\dots, \alpha_n \right)= \left(\alpha_1,\dots, \alpha_m,\alpha_{m+1},\dots,\alpha_n \right) $. Если мы произвольным образом выберем подмножество $ \{\alpha_1,\dots, \alpha_m \} $ из множества $ \{\alpha_1,\dots, \alpha_n \} $, то, тем самым, установим и оставшиеся элементы: $ \alpha_{m+1},\dots,\alpha_n $. Таким образом, общее число всех перестановок из $ n_{} $ элементов равно произведению числа $ x_{} $ способов, которыми выбираются элементы $ \alpha_1,\dots, \alpha_m $, на число перестановок этих чисел и на число перестановок чисел $ \alpha_{m+1},\dots,\alpha_n $. Используем теорему из предыдущего пункта: $$ n!=x\cdot m! \cdot (n-m)! . $$ ♦

или BIBD ☞ ЗДЕСЬ