== Элементы комбинаторики== ~~TOC~~ **Комбинаторикой** или **комбинаторным анализом** называется раздел математики, посвященный решению задач выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами. === Перестановки == Пусть имеется множество, состоящее из $ n_{} $ элементов. Упорядочим их определенным образом и каждое такое упорядочение назовем **перестановкой**[[(англ.) permutation]] этих элементов. !!П!! **Пример.** Рассмотрим буквы а д к л о . Перестановкой этих букв является любое пятибуквенное слово, состоящее исключительно только из этих букв и, к тому же без их повторений. Например, перестановками будут слова //лодка//, //оклад//, //дклоа// и т.п. (неважно осмысленны они или нет). !!П!! **Пример.** Перестановка в колоде игральных карт ♦, ♣, ♥, ♠ получается их тасованием. **Задача.** Сколько всего существует перестановок $ n_{} $ элементов? Для ответа на этот вопрос сформируем сначала гипотезу. Для $ n_{}=1 $ существует только одна перестановка. Для $ n_{}=2 $ имеем две: а, д $ \rightarrow $ а д и д а . Для $ n_{}=3 $ получаем уже шесть: к, л, о $ \rightarrow $ к л о , к о л , л к о , л о к , о к л , о л к . !!Т!! **Теорема 1.** //Число всех перестановок из// $ n_{} $ //элементов равно// $ n_{}! $. **Доказательство** проводится ((:basics:induction методом математической индукции)). Для $ 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)! $ элементов. ♦ ====Перестановки, генерируемыми функциями в модулярной арифметике== !!§!! Pаздел МОДУЛЯРНАЯ АРИФМЕТИКА ☞ ((:modular ЗДЕСЬ)). Линейные по $ x $ функции $$ ax+b \pmod{p} \quad \mbox{при} \ \{a\ne 0,b\} \in \{0,1,2,\dots,p-1\} $$ и $ p $ --- ((:numtheory#prostye_chisla простом)) генерируют перестановки чисел $0,1,2,\dots,p-1 $. Все эти перестановки различны. !!П!! **Пример.** $a=5,b=2,p=7$ $$ \begin{array}{c|c|c|c|c|c|c|c} x & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline ax+b \pmod{p} & 5 & 1 & 4 & 0 & 3 & 6 & 2 \end{array} $$ ♦ Степенные по $ x $ функции $$ x^{a} \pmod{M} \quad \mbox{при} \quad M=p_1p_2 \ \mbox{и} \ a\in \{0,1,\dots, (p_1-1)(p_2-1)-1\}, \operatorname{HOD} (a, (p_1-1)) =1,\ \operatorname{HOD} (a, (p_2-1)) =1 $$ и простых различных $p_1,p_2$ генерируют перестановки чисел $0,1,2,\dots,M-1 $. Не все эти перестановки различны. !!П!! **Пример.** $a=7,M=15$ $$ \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ \hline x^{a} \pmod{M} & 0 & 1 & 8 & 12 & 4 & 5 & 6 & 13 & 2 & 9 & 10 & 11 & 3 & 7 & 14 \end{array} $$ Функция $ x^{11} \pmod{15} $ имеет ту же таблицу значений. ♦ ==== Перестановки чисел 1,2,...,n == !!§!! Вспомогательный материал к пункту ☞ ((:algebra2:dets#определение ОПРЕДЕЛЕНИЕ ОПРЕДЕЛИТЕЛЯ)) Упорядоченная пара $ (a,b) $ различных натуральных чисел **образует инверсию** (или нарушение порядка) если $ a>b $. Можно ввести ''счетчик'' инверсий: $$\operatorname{inv}(a,b)= \left\{ \begin{array}{cc} 1 & \iff a>b ; \\ 0 & \iff a 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 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_{} $) элементов. Хотя мы и записываем такие подмножества, каким-то образом расставляя их элементы, но порядок их следования несуществен. Каждую такую выборку назовем **сочетанием из**[[(англ.) combination]] $ \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)! . $$ ♦ Хотя это и следует из доказательства, на первый взгляд, не очевидно, что число $$ \frac{n!}{m!(n-m)!}=\frac{n(n-1)\times \dots \times (n-m+1)} {1\times \dots \times m} $$ является целым, т.е. что произведение произвольных подряд идущих $ m_{} $ целых чисел делится на $ m_{}! $. Независимое доказательство этого факта приводится ☞ ((:numtheory#каноническое_разложение_числа ЗДЕСЬ)). Число $$ \frac{n!}{m!(n-m)!} $$ также известно как **биномиальный коэффициент**. Подробнее ☞ ((:binomial ЗДЕСЬ)). ===Cбалансированная неполная блок-схема== или BIBD ☞ ((:basics/combinatorics/kirkman#sbalansirovannaja_nepolnaja_blok-sxema ЗДЕСЬ))