Комбинаторика: сочетания, размещения, перестановки
Два вопроса определяют формулу: важен ли порядок и можно ли повторять элементы. Разбираем все четыре случая на понятных примерах.
Два вопроса, которые решают всё
Прежде чем брать формулу, ответьте на два вопроса о задаче:
- Важен ли порядок выбранных элементов?
- Можно ли брать один элемент несколько раз?
Четыре комбинации ответов дают четыре формулы — больше в базовой комбинаторике ничего не нужно.
Порядок не важен, повторов нет: сочетания
Выбрать 3 человека из 10 в комиссию. Неважно, в каком порядке их назвали — состав один и тот же. Ответ: 120 вариантов.
Сюда же относятся лотереи: выбор 6 номеров из 45 не зависит от порядка их называния.
Порядок важен, повторов нет: размещения
Из тех же 10 человек выбрать председателя, заместителя и секретаря. Здесь порядок меняет результат: Иванов председателем и Петров замом — не то же самое, что наоборот. Ответ: 720 вариантов.
Обратите внимание на связь: 720 = 120 × 6, где 6 = 3! — число способов расставить трёх выбранных по должностям. Размещения всегда равны сочетаниям, умноженным на факториал.
Порядок важен, повторы можно
Четырёхзначный пин-код из цифр 0–9: на каждой позиции любая из 10 цифр, повторы разрешены. Ответ: 10⁴ = 10 000 вариантов.
Российский автомобильный номер использует 12 букв, похожих в кириллице и латинице, и три цифры: вариантов получается 12 × 10 × 10 × 10 × 12 × 12 = 1 728 000 на один регион.
Порядок не важен, повторы можно
Выбрать 3 шарика мороженого из 10 вкусов, разрешая одинаковые. Ответ: C(12,3) = 220. Этот случай встречается реже и чаще всего вызывает затруднения — его удобно представлять как распределение шаров по ящикам.
Перестановки
Частный случай размещений, когда берутся все элементы: n! вариантов. Пять человек в очереди можно расставить 120 способами, десять — уже больше трёх с половиной миллионов.
Факториал растёт чудовищно быстро: 20! превышает два квинтиллиона. Отсюда и вычислительная сложность задач вроде коммивояжёра — полный перебор невозможен уже при нескольких десятках точек.
Правило суммы и правило произведения
- Правило произведения: если выбор состоит из независимых шагов, число вариантов перемножается. Три блузки и четыре юбки дают 12 комплектов;
- Правило суммы: если варианты взаимоисключающие, они складываются. Доехать поездом (3 рейса) или автобусом (5 рейсов) — 8 способов.
Практически любая сложная задача разбирается через сочетание этих двух правил. Если запутались, опишите словами последовательность выборов — структура решения станет видна.
Частые вопросы
Существует ровно один способ упорядочить пустое множество. Такое определение делает формулы согласованными: C(n,n) = n!/(n!·0!) = 1, что и должно быть.
Спросите себя, возвращается ли элемент обратно. Вынимаем шар и не кладём назад — повторов нет. Записываем цифру и снова можем её использовать — повторы есть.