== Элементы комбинаторики==
~~TOC~~
**Комбинаторикой** или **комбинаторным анализом** называется раздел математики,
посвященный решению задач выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами.
=== Перестановки ==
Пусть имеется множество, состоящее из $ n_{} $ элементов. Упорядочим их определенным
образом и каждое такое упорядочение назовем **перестановкой** этих элементов.
!!П!! **Пример.** Рассмотрим буквы
а
д
к
л
о
. Перестановкой
этих букв является любое пятибуквенное слово, состоящее исключительно только из этих букв
и к тому же без их повторений. Например, перестановками будут слова
//лодка//, //оклад//, //дклоа// и т.п. (неважно осмысленны они или нет).
!!П!! **Пример.** Перестановка в колоде игральных карт
♦,
♣,
♥,
♠
получается их тасованием.
**Задача.** Сколько всего существует перестановок $ 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)! $ элементов.
♦
==== Перестановки чисел {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.