Сочетания
Неупорядоченные выборки $k$ объектов из $n$ различных объектов (без повторений)
1. Что такое сочетание?
Сочетание — это способ выбора подмножества элементов из большего множества, при котором важен только состав группы, а не порядок, в котором элементы были выбраны.
Ключевая идея: Когда мы выбираем подмножество из $k$ элементов из множества, содержащего $n$ элементов, нас интересует, какие элементы выбраны, а не в каком порядке они были взяты.
Примеры из жизни
- Комитеты: Выбор 3 человек из 10 для формирования комитета — группа {Аня, Борис, Вера} остаётся той же, независимо от того, кого выбрали первым.
- Карточные комбинации: Покерная рука из 5 карт из колоды в 52 карты — набор {Т♠, К♥, Д♦, В♣, 10♠} одинаков вне зависимости от порядка раздачи.
- Начинки для пиццы: Выбор 3 начинок из меню с 8 вариантами — пепперони-грибы-оливки — это та же пицца, что и оливки-пепперони-грибы.
- Лотерейные числа: Выбор 6 чисел из 49 — выигрышный набор одинаков независимо от порядка розыгрыша.
Порядок не имеет значения
Выбираем {A, B, C} из {A, B, C, D, E}:
| Расположение | Одно и то же сочетание? |
|---|---|
| A, B, C | ✓ Все это — одно и то же сочетание {A, B, C} |
| A, C, B | |
| B, A, C | |
| B, C, A | |
| C, A, B | |
| C, B, A |
Эти 6 = $3!$ расположений объединяются в одно сочетание.
2. Вывод формулы сочетаний
Пошаговый вывод
Нам уже известна формула размещений для выбора и упорядочивания $k$ элементов из $n$:
$$ P(n,k) = \frac{n!}{(n-k)!} $$При этом каждое сочетание (неупорядоченная группа) из $k$ элементов может быть внутренне переставлено $k!$ способами. Поэтому общее число размещений равно числу сочетаний, умноженному на число внутренних перестановок: