Сочетания.

Определение. Сочетанием из различных элементов по элементов называется набор каких-либо из этих элементов без учета порядка их следования.

Два сочетания из по считаются различными, если они различаются составом входящих в них элементов.

Пример. Все сочетания из пяти элементов – цифр 1, 2, 3, 4, 5 по два:

(1, 2); (1, 3); (1, 4); (1, 5); (2, 3); (2, 4); (2, 5); (3, 4); (3, 5); (4, 5).

Число сочетаний из по принято обозначать через . Последний пример показывает, что .

Теорема. Для числа сочетаний справедлива формула:

. (3)

Доказательство. Размещения из по с одинаковым составом элементов, но разным порядком их следования, образуют перестановки из элементов, число которых, согласно формуле (1), равно .

Все эти перестановки приводят к одному сочетанию с тем же составом элементов. Поэтому число сочетаний из по в раз меньше, чем число размещений из по : . Второе равенство в формуле (3) следует теперь из (2). ▄

Примеры. 1) .

2) .

3) .

4) .

Числа называют биномиальными коэффициентами, поскольку они участвуют в разложении бинома (двучлена) по степеням (бином Ньютона):

.

Частными случаями разложения бинома являются хорошо известные формулы для квадрата и куба суммы.

Примеры. 1) Число способов, которыми можно заполнить карточку спортлото «5 из 36», есть число способов, которыми из 36 имеющихся чисел можно выбрать 5 для зачеркивания. Поскольку порядок зачеркивания выбранных чисел не играет роли, мы имеем дело с сочетаниями из 36 по 5. Число способов выражается числом сочетаний:

.

2) Число способов, которыми можно заполнить карточку спортлото «5 из 36», угадав ровно три номера, найдем с помощью принципа умножения. Три выигрышных («угаданных») номера должны быть выбраны из шести выигрышных номеров; это можно сделать способами. Два оставшихся номера должны быть выбраны из тридцати одного невыигрышного номера; это можно сделать способами. Поэтому общее число способов .

3) Число способов, которыми в серии испытаний из бросаний монет может ровно раз выпасть герб – это число способов, которыми из номеров испытаний можно выбрать номеров для успешных испытаний. Поскольку порядок, в котором назначаются номера успешных испытаний, не играет роли, мы имеем дело с сочетаниями. Поэтому .