Формулы числа сочетаний без повторений

Число всех сочетаний без повторений по m из n элементов обозначается .

Буква C от французского «combinaison» («сочетание»).

Теорема. .

Доказательство. Каждое размещение без повторений (x ₁,…, x_m) по m из n можно построить в 2 шага: вначале строится сочетание без повторений { x ₁,…, x_m } по m из n, а затем – перестановка (x ₁,…, x_m) из m элементов множества { x ₁,…, x_m }. По правилу произведения

Из теоремы и формул для числа размещений без повторений следуют еще 2 формулы для числа сочетаний без повторений:

.

.