Сочетания
Сочетания. § 11. Элементы комбинаторики. Алгебра 9 класс. Макарычев
§ 11. Элементы комбинаторики
Сочетания
Пусть имеются пять гвоздик разного цвета. Обозначим их буквами а, 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. Выясним сначала, как 
выражается через 
и Р3. Мы нашли, что из 5 элементов можно составить следующие сочетания по 3 элемента:
-
abc, abd, abe, acd, асе, ade, bed, bee, bde, cde.
В каждом сочетании выполним все перестановки. Число перестановок из трех элементов равно Р3. В результате получим все возможные комбинации из 5 элементов по 3, которые различаются либо самими элементами, либо порядком элементов, т. е. все размещения из 5 элементов по 3. Всего мы получим размещений.
Значит,
Отсюда
Аналогично будем рассуждать в общем случае. Допустим, что имеется множество, содержащее n элементов, и из его элементов составлены все возможные сочетания по k элементов. Число таких сочетаний равно . В каждом сочетании можно выполнить Рk перестановок. В результате мы получим все размещения, которые можно составить из n элементов по k. Их число равно 
Значит,
Отсюда
Пользуясь тем, что 
где k ≤ n, находим, что
Мы получили формулу для вычисления числа сочетаний из п элементов по k при любом k ≤ n.
Приведем примеры.
Пример 1. Из набора, состоящего из 15 красок, надо выбрать 3 краски для окрашивания шкатулки. Сколькими способами можно сделать этот выбор?
Каждый выбор трех красок отличается от другого хотя бы одной краской. Значит, здесь речь идет о сочетаниях из 15 элементов по 3.
Имеем
Следовательно, 3 краски можно выбрать 455 способами. 
Продолжение >>>