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


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

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

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

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

П

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

П

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

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

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

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

Т

Теорема. Число всех перестановок из 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)! элементов.

Сочетания

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

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

П

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

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

Т

Теорема. Число сочетаний из 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)!}

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


2017/04/04 20:20 редактировал au