Сочетания без повторений

Если из всех размещений, которые можно составить из элементов по , мы отберём только те, которые одно от другого разнятся по крайней мере одним элементом, то получим соединения, которые называются сочетаниями и обозначается .

Другими словами, если две выборки, отличающиеся только порядком записи символов, считают совпадающими, то говорят о сочетании из m элементов по k.

Например, из четырёх элементов сочетания по 3 будут:

.

Если в каждом из этих соединений сделаем всевозможные перестановки, то получим всевозможные размещения из четырёх элементов по 3:

Число таких размещений равно, очевидно, .

Таким образом, число всех размещений из элементов по равно числу всех сочетаний из элементов по , умноженному на число всех перестановок, какие можно сделать из элементов, т.е. . Отсюда