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

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

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

Теорема. .

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

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

.

.