1. Число перестановок
Рассмотрим следующую задачу: имеется n последовательно расположенных неодинаковых элементов. Требуется найти количество способов, которыми их можно переставить.
(восклицательным знаком обозначается факториал)
2. Число сочетаний
Имеется n различных (неодинаковых, неповторяющихся) элементов. Требуется выбрать из них m элементов, безразлично, в каком порядке.
Число сочетаний используется в формуле бинома Ньютона для определения биномиальных коэффициентов. В школе каждый заучивал формулы квадрата и куба суммы двух чисел:
(a+b)2=a2+2ab+b2
(a+b)3=a3+2a2b+2ab2+b3
Для произвольной степени формула выглядит так:
Как мы видим, коэффициенты относительно краев выражения симметричны:
Cnn=Cn0=1, Cn-1n=C1n=n, Cnn-2=Cn2=n(n-1)/2!, Cnn-3=Cn3=n(n-1)(n-2)/3!, и т.д.
3. Число размещений
Так же, как и в предыдущем примере, имеется n различных элементов. Нужно выбрать из них m элементов, причем порядок расположения элементов важен!
4. Основная формула комбинаторики
До сих пор мы рассматривали комбинации с неповторяющимися элементами. Рассмотрим теперь случай, когда они могут повторяться.
Пусть имеется k групп элементов, каждая численностью соответственно n1, n2, ..., nk. Выберем по одному элементу из каждой группы. Тогда общее число всех возможных комбинаций вычисляется по следующей формуле.
Если n1 = n2 = ... = nk, то формула приобретает вид
5. Статистика Бозе-Эйнштейна
Предположим, что r неразличимых (одинаковых) частиц распределяются по k ячейкам (r ≤ k). Сколькими способами их можно распределить?
Пусть в какую-то определённую ячейку попало ровно m частиц. Подсчитаем количество вариантов, которыми оставшиеся r-m частиц могут быть распределены по k-1 оставшимся ячейкам.
Тогда вероятность того, что в определённую ячейку попало ровно m частиц, равна
Такое рапределение носит в физике название статистики Бозе-Эйнштейна, ей описывается поведение фотонов, атомных ядер и атомов, содержащих чётное количество частиц.
6. Число перестановок с повторениями
Имеется k групп элементов, по ni элементов в каждой группе. Внутри каждой группы элементы одинаковы (неразличимы). Сколькими способами можно переставить эти n1 + n2 + ... + nk элементов?
Если бы элементы в группе не повторялись, то мы бы нашли общее количество всех элементов и вычислили бы факториал этого числа. Но для каждой группы каждые ni! перестановок преобразуются в одну (элементы ведь неразличимы), и число перестановок уменьшается каждый раз в ni! раз. В итоге получаем:
