13. Сочетания: сколько способов выбрать r из n
Сочетание (без повторений) — это выбор разных элементов из без учёта порядка. Каждое такое сочетание можно упорядочить способами и получить разных размещений. Поэтому число сочетаний равно числу размещений, делённому на : .
Что пригодится из прошлого: размещения — число упорядоченных выборок ; перестановки и факториал — сколько способов упорядочить элементов и как сокращать дроби с факториалами. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Выбрать двоих или выбрать двоих «с должностями»
Из четырёх человек нужно выбрать двоих. Есть две разные задачи:
- староста и заместитель — порядок важен, это размещения: способов;
- двое дежурных — порядок не важен, это сочетания. Сколько их?
Выпишем все двенадцать размещений и посмотрим, как они группируются:
- {a, b} → ab, ba — размещений: 2
- {a, c} → ac, ca — размещений: 2
- {a, d} → ad, da — размещений: 2
- {b, c} → bc, cb — размещений: 2
- {b, d} → bd, db — размещений: 2
- {c, d} → cd, dc — размещений: 2
Каждая пара людей породила ровно два размещения (кто староста, кто заместитель). Групп столько, сколько способов выбрать двоих; в каждой группе размещения. Поэтому
То же для троих из четырёх:
- {a, b, c} → abc, acb, bac, bca, cab, cba — размещений: 6
- {a, b, d} → abd, adb, bad, bda, dab, dba — размещений: 6
- {a, c, d} → acd, adc, cad, cda, dac, dca — размещений: 6
- {b, c, d} → bcd, bdc, cbd, cdb, dbc, dcb — размещений: 6
Четыре группы по размещений: , поэтому .
Формула
Теорема. Число сочетаний без повторений из элементов по равно
Доказательство. Рассмотрим все сочетания без повторений из элементов по и упорядочим каждое из них всеми возможными способами. Получаются размещения без повторений. Проверим, что мы ничего не потеряли и не посчитали дважды:
- каждое сочетание даёт различных размещений (все перестановки его элементов);
- разные сочетания дают разные размещения: по размещению однозначно восстанавливается набор его элементов;
- каждое размещение получено ровно из одного сочетания: достаточно «забыть порядок».
Значит, размещения без повторений разбились на группы по штук, и групп столько, сколько существует сочетаний:
Разделим на и вспомним, что (глава про перестановки):
Как читать запись. читается «число сочетаний из по » или « из по ». Её же записывают . Верхнее число — сколько элементов в запасе, нижнее — сколько выбираем. Это не дробь .
Как считать на практике
Большие факториалы считать не нужно. В числителе напишите множителей, начиная с и уменьшая на единицу, в знаменателе — , и сокращайте.
Для большого числа элементов получаются знакомые цифры:
- лотерея «6 из 49»: ;
- набор из пяти карт из колоды в 52 карты: .
Особые значения
- : выбрать ничего можно одним способом (взять пустой набор).
- : выбрать один элемент можно способами.
- : выбрать всё можно одним способом.
- при : нельзя выбрать различных элементов из , поэтому способов нет.
Сочетание или размещение?
Комиссия из трёх человек из десяти: порядок не важен, . Председатель, заместитель и секретарь из тех же десяти: должности разные, порядок важен, . Видим связь: . Каждой комиссии отвечают способов раздать должности.
Когда «выбираем» связывается с «и»
Задача. В классе мальчиков и девочек. Сколькими способами можно выбрать делегацию из двух мальчиков и двух девочек?
Выбор мальчиков и выбор девочек — два шага подряд; число способов каждого шага не зависит от результата другого. По правилу произведения
Частые ошибки
- Делить на дважды или забыть поделить. Размещения — без деления, сочетания — с делением на , и один раз.
- Принимать за дробь . — число способов, например , а не .
- Применять формулу, когда порядок важен. Если в задаче есть должности, места, номера — это размещение.
- Забыть . Тогда сочетаний без повторений нет.
Проверь себя
1. Вычислите .
Решение
.
2. Из двенадцати игроков нужно выбрать стартовую пятёрку. Сколько способов?
Решение
Порядок не важен: .
3. Из семи человек нужно выбрать комиссию из трёх человек и затем одного из них назначить председателем. Сколько способов?
Решение
Первый путь. Сначала комиссия: способов. Затем председатель среди выбранных: способа. Всего .
Второй путь. Сначала председатель: способов. Затем два остальных члена из оставшихся шести: . Всего . Ответы совпали — хорошая проверка.
4. В лотерее «6 из 49» нужно угадать шесть чисел. Сколько существует различных вариантов выбора шести чисел из ?
Решение
Порядок не важен: .
Итог
- Сочетание — выбор элементов из без учёта порядка.
- Каждое сочетание без повторений порождает размещений, поэтому .
- Считайте сокращением: множителей сверху, снизу.
- , , при .
