УказательРазделыОбозначенияАвторО проекте


Элементы комбинаторики

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

Перестановки

Пусть имеется множество, состоящее из 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)! элементов.

Перестановки чисел {1,2,...,n}

§

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

Упорядоченная пара (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{RubineRed} \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{RubineRed} \alpha },c_1,\dots,c_M)

Говорят, что перестановка \Xi получена из перестановки \Theta в результате транспозиции.

Т

Теорема 2. Любая транспозиция меняет четность перестановки:

\operatorname{inv} \Theta - \operatorname{inv} \Xi =нечетное число\, .

Доказательство. I. Предположим сначала, что L=0, т.е. производится транспозиция соседних элементов.

\operatorname{inv} \Theta = \operatorname{inv} (a_1,\dots,a_K,{\color{RubineRed} \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{RubineRed} \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{RubineRed} \alpha },{\color{DarkGreen} \beta })+ \sum_{1\le \ell \le M}\operatorname{inv}({\color{RubineRed} \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{RubineRed} \alpha }). Поэтому

\operatorname{inv} \Theta - \operatorname{inv} \Xi =\operatorname{inv} ({\color{RubineRed} \alpha },{\color{DarkGreen} \beta })- \operatorname{inv} ({\color{DarkGreen} \beta },{\color{RubineRed} \alpha })= \pm 1.

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

2N+1=p+q, \quad и \ \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{RubineRed} \alpha }, b_1,\dots,b_{L},{\bf \beta},c_1,\dots,c_M) =\operatorname{inv} (a_1,\dots,a_K,b_1,{\color{RubineRed} \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{RubineRed} \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{RubineRed} \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{RubineRed} \alpha },c_1,\dots,c_M) + \quad +\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{RubineRed} \alpha },c_1,\dots,c_M) +\omega_1+\dots+\omega_{2L+1}= \operatorname{inv} \Xi + нечетное число\, .

Т

Теорема 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)! .

§

Хотя это и следует из доказательства, на первый взгляд, не очевидно, что число

\frac{n!}{m!(n-m)!}=\frac{n(n-1)\times \dots \times (n-m+1)} {1\times \dots \times m}

является целым, т.е. что произведение произвольных подряд идущих m_{} целых чисел делится на m_{}!. Независимое доказательство этого факта приводится ЗДЕСЬ.

§

Число

\frac{n!}{m!(n-m)!}

также известно как биномиальный коэффициент. Подробнее ЗДЕСЬ.


2019/11/15 23:53 редактировал au