combinatorics.md

Комбинаторика

Иногда в задачах требуется подсчитать количество некоторых объектов, количество способов сделать что-то. При этом обычно это количество слишком велико, чтобы можно было перечислить все объекты в явном виде.

Например, можно посчитать количество перестановок из $n$ различных элементов следующим образом. Понятно, что на первое место в перестановке мы можем поставить любой из $n$ элементов, на второе — любой из $n - 1$ оставшихся, и так далее. Для последнего места останется только 1 элемент. Значит, число перестановок $n$ элементов равно $n\cdot(n-1)\cdot\ldots\cdot2\cdot1$, что сокращенно обозначается как $n!$

Принято считать, что $0!=1$

Биномиальные коэффициенты

Посчитаем количество способов выбрать $k$ элементов из $n$ различных (называется числом сочетаний из $n$ по $k$ и обозначается $C_n^k$). Точно так же на первое место мы можем поставить любой из $n$ элементов, на второе — любой из $n - 1$ оставшихся, на $k$-е место останется $n - k + 1$ вариант, то есть всего вариантов получится $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)=\frac{n!}{(n-k)!}$. Заметим, что так мы посчитали число упорядоченных наборов из $k$ элементов и чтобы получить количество способов выбрать $k$ элементов из $n$ нужно поделить результат на $k!$, ведь, как было установлено ранее, именно столько есть спобосов упорядочить $k$ элементов. В итоге получается $C_n^k=\frac{n!}{k!(n-k)!}$

Есть и другой способ подсчета $C_n^k$ для $0 < k < n$. Посмотрим на первый элемент. Если он входит в набор, то осталось выбрать $k-1$ из $n-1$ оставшихся. Иначе нужно выбрать $k$ из $n-1$ оставшихся. Значит, $C_n^k=C_{n-1}^{k}+C_{n-1}^{k-1}$. Так можно найти все $C_n^k$ до какого-то $n$ за $O(n^2)$.

Таким образом, $C_n^k$ легко представлять в виде бесконечного треугольника, где на сторонах стоят 1, а остальные числа равны сумме двух верхних. Легко видеть, что $C_n^k$ это $k$-е число в строке номер $n$. Это называют треугольником Паскаля.

Число путей черепашки

Пусть, в левом верхнем углу прямоугольного поля стоит черепашка, которая может ходить только на одну клетку вправо или вниз. Сколько у нее способов попасть в правый нижний угол?

Бином Ньютона

Рассмотрим разложение выражения $(a+b)^n$. Докажем, что коэффициент при $a^kb^{n-k}$ равен $C_n^k$. Действительно $(a+b)^n=(a+b)(a+b)\cdots(a+b)~$($n$ раз). Чтобы получить член $a^kb^{n-k}$ надо из $k$ скобок выбрать $a$, а из остальных $b$. Как мы уже знаем, это можно сделать $C_n^k$. Значит, $(a+b)^n=\sum\limits_{k=0}^nC_n^ka^kb^{n-k}$.

Из этого следует, что коэффициенты при разложении $(a+b)^n$ являются строкой треугольника Паскаля.

Бином Ньютона часто используется для доказательства различных комбинаторных формул.

##Полиномиальные коэффициенты

Посчитаем теперь количество разбиений множества на $m$ множеств размеров $k_1,k_2\ldots,k_m$. Это называется полиномиальные коэффициенты и обозначается $C(k_1,k_2,\ldots,k_m)$ Будем набирать эти множества по очереди. Количество способов выбрать первое подмножесто равно $C_n^{k_1}$, второе $C_{n-k_1}^{k_2}$ и так далее. Итоговая формула $C(k_1,k_2,\ldots,k_m)=C_n^{k_1}\cdot C_{n-k_1}^{k_2}\cdots C_{k_m}^{k_m}=\frac{n!}{k_1!k_2!\cdots k_m!}$.

Аналогично биному Ньютона, такие числа являются коэффициентами при членах $x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m}$ выражения $(x_1+\ldots+x_m)^n$. Доказательство тоже аналогично доказательству из предыдущего раздела и оставляется в качестве упражнения.

Числа Каталана

Посчитаем количество правильных скобочных последовательностей (ПСП). Интуитивно понятно, что это, но формально они определятюся так:

• Пустая последовательность является ПСП
• Если $A$ является ПСП, то $(A)$ является ПСП
• Если $A$ и $B$ являются ПСП, то $AB$ является ПСП.

Теперь, посчитаем количество ПСП с $2n$ скобками. Это называется числами Каталана и обозначается $C_n$. Рассмотрим первое место, где разность количества открывающих и закрывающих скобок впервые становится равна 0 и часть ПСП до этого места обозначим $(A)$, а часть после обозначим $B$. Понятно, что $A$ и $B$ являются ПСП меньшего размера (возможно, пустыми).

Теперь $C_n$ посчитать легко, перебирая размер $A$.

$C_0=1$

$C_n=C_0C_{n-1}+C_1C_{n-2}+\ldots+C_{n-1}C_0$

Полезные формулы

• $C_n^k=C_n^{n-k}$
• $C_n^0+C_n^1+C_n^2+\ldots+C_n^n=2^n$
• $C_n^0-C_n^1+C_n^2-\ldots+(-1)^nC_n^n=0$
• $C_n=\frac{1}{n+1}C_{2n}^n$

В качестве упражнения попробуйте их доказать.