Иногда в задачах требуется подсчитать количество некоторых объектов, количество способов сделать что-то. При этом обычно это количество слишком велико, чтобы можно было перечислить все объекты в явном виде.
Например, можно посчитать количество перестановок из \(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\)
В качестве упражнения попробуйте их доказать.