Основы комбинаторики

Зачем считать варианты

Комбинаторика помогает посчитать количество возможных вариантов без длинного перебора. В вероятности это число часто становится знаменателем дроби $\frac{m}{n}$.

Правило умножения

Если первое действие можно выполнить $a$ способами, а после каждого из них второе — $b$ способами, то оба действия можно выполнить

$a\cdot b$

способами.

Пример. Есть $3$ футболки и $2$ пары брюк. Собрать комплект можно $3\cdot2=6$ способами.

Для трёх и более шагов множители продолжают перемножаться. Четырёхзначный PIN-код содержит $10^4=10\,000$ вариантов, если цифры могут повторяться и код может начинаться с нуля.

Повторения и порядок

Перед решением задайте два вопроса:

1. Можно ли повторять элементы?
2. Важен ли порядок?

Коды $12$ и $21$ различны, поэтому для кодов порядок важен. Но группа из Айбека и Нуры остаётся той же группой, как бы мы ни перечислили имена: при выборе группы порядок не важен.

Перестановки

Число способов расставить $n$ различных объектов:

$n!=1\cdot2\cdot3\cdots n$

Например, три разные книги можно расположить $3!=6$ способами, а четыре — $4!=24$ способами.

Выбор ролей

Если из $7$ учеников выбирают капитана и его заместителя, порядок важен: один и тот же ученик не может занять обе роли.

$7\cdot6=42$

Если же выбирают просто двух участников из пяти и роли одинаковы, каждая пара при прямом подсчёте появляется дважды. Поэтому

$\frac{5\cdot4}{2}=10$

Дерево вариантов

Когда формула не очевидна, нарисуйте дерево: от каждого выбора проведите ветви ко всем возможным следующим выборам. Число конечных ветвей даст ответ и поможет не пропустить варианты.

ОРТ-совет: слова «код», «номер», «капитан и заместитель» обычно означают, что порядок важен. Слова «группа», «команда из двух», «выбрать двоих» обычно означают, что порядок не важен.