Сочетания

Пусть имеются пять гвоздик разного цвета. Обозначим их буквами а, b, с, d, е. Требуется составить букет из трех гвоздик. Выясним, какие букеты могут быть составлены.

Если в букет входит гвоздика а, то можно составить такие букеты:

abc, abd, abe, acd, асе, ade.

Если в букет не входит гвоздика а, но входит гвоздика b, то можно получить такие букеты:

bed, bee, bde.

Наконец, если в букет не входит ни гвоздика а, ни гвоздика b, то возможен только один вариант составления букета:

cde.

Мы указали все возможные способы составления букетов, в которых по-разному сочетаются три гвоздики из данных пяти. Говорят, что мы составили все возможные сочетания из 5 элементов по 3.

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

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

Число сочетаний из п элементов по k обозначают (читается: «С из n по k»).

В рассмотренном примере, составив все сочетания из 5 элементов по 3, мы нашли, что

Выведем формулу числа сочетаний из п элементов по k, где k ≤ n. Выясним сначала, как выражается через и Р₃. Мы нашли, что из 5 элементов можно составить следующие сочетания по 3 элемента:

abc, abd, abe, acd, асе, ade, bed, bee, bde, cde.

В каждом сочетании выполним все перестановки. Число перестановок из трех элементов равно Р₃. В результате получим все возможные комбинации из 5 элементов по 3, которые различаются либо самими элементами, либо порядком элементов, т. е. все размещения из 5 элементов по 3. Всего мы получим размещений.

Значит,

Отсюда

Аналогично будем рассуждать в общем случае. Допустим, что имеется множество, содержащее n элементов, и из его элементов составлены все возможные сочетания по k элементов. Число таких сочетаний равно . В каждом сочетании можно выполнить Р_k перестановок. В результате мы получим все размещения, которые можно составить из n элементов по k. Их число равно

Значит,

Отсюда

Пользуясь тем, что где k ≤ n, находим, что

Мы получили формулу для вычисления числа сочетаний из п элементов по k при любом k ≤ n.

Приведем примеры.

Пример 1. Из набора, состоящего из 15 красок, надо выбрать 3 краски для окрашивания шкатулки. Сколькими способами можно сделать этот выбор?

Каждый выбор трех красок отличается от другого хотя бы одной краской. Значит, здесь речь идет о сочетаниях из 15 элементов по 3.

Имеем

Следовательно, 3 краски можно выбрать 455 способами.

Продолжение >>>