5.4. Сочетания

Сочетаниями из n элементов по m элементов называются любые подмножества, состоящие из m элементов, которые принадлежат множеству, состоящему из n различных элементов.

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

Число сочетаний из n элементов по m элементов обозначается (читается "C из n по m").

Теорема. Число сочетаний из элементов по равно , т. е.

Доказательство. Выведем формулу для подсчета числа сочетаний. Пусть имеется множество Q_n и нужно образовать упорядоченное подмножество множества Q_n, содержащее m элементов (то есть образовать размещение). Делаем это так:

1) выделим какие-либо m элементов из n элементов множества Q_n Это, согласно сказанному выше, можно сделать способами;

2) упорядочим выделенные m элементов, что можно сделать способами. Всего можно получить вариантов (упорядоченных подмножеств), откуда следует: , то есть

.

Пример. Из семи заводов организация должна выбрать три для размещения трех заказов. Сколькими способами можно разместить заказы?

Решение. Способ размещения заказов определяется выбором тройки заводов, так как все эти заводы получат одинаковые заказы, и число вариантов определяется как число сочетаний.

.

Следствие. Число сочетаний из n элементов по n – m равно числу сочетаний из n элементов по m , то есть

=

В выражении для поменяем местами сомножители m! и (n – m)!; в результате имеем

Пример. Имеется 10 белых и 5 черных шаров. Сколькими способами можно выбрать 7 шаров, чтобы среди них были 3 черных?

Решение. Среди выбранных шаров 4 белых и 3 черных.

Белые шары можно выбрать способами.

Черные шары можно выбрать .

Тогда по правилу умножения искомое число способов равно =2100.

Докажем два свойства числа сочетаний, которые могут быть полезными при решении комбинаторных задач.

Теорема. Имеет место равенство (правило Паскаля)

1 ≤ m < n .

Доказательство. Имеем

Теорема. Имеет место равенство

Это свойство иногда формулируется в виде следующей теоремы о конечных множествах:

Число всех подмножеств множества, состоящего из n элементов равно 2ⁿ.

Пример. Сколько существует вариантов опроса 11 студентов на одном занятии, если ни один из них не будет подвергнут опросу дважды и на занятии может быть опрошено любое количество студентов, причем порядок, в котором опрашиваются студенты, безразличен?

Решение. Преподаватель может не спросить ни одного из 11 студентов, что является одним из вариантов. Этому случаю соответствует . Преподаватель может опросить только одного из студентов. Таких вариантов . При опросе двух студентов вариантов будет , трех - и так далее. Наконец, могут быть опрошены все студенты. Число вариантов в этом случае равно . Тогда по правилу сложения число всех возможных вариантов опроса равно

+ + + + … + .

С другой стороны, для каждого из студентов существует две возможности: он будет опрошен или не опрошен на данном занятии. Другими словами, каждую из 11 операций, заключающихся в том, что каждый студент будет либо опрошен, либо не опрошен, можно выполнить по правилу умножения 2·2·2·2· … ·2 = 2¹¹ способами, что и следовало ожидать, так как

+ + + + … + = 2¹¹ .