Перестановки и сочетания: объяснение

Правило произведения

Комбинаторные задачи спрашивают, сколькими способами может что-то произойти. Основа — правило произведения: если один выбор можно сделать $m$ способами, а второй, независимый, — $n$ способами, то оба вместе можно сделать $m \times n$ способами. Идея работает для любого числа этапов.

Имея 3 рубашки, 4 пары брюк и 2 пары обуви, можно составить $3 \times 4 \times 2 = 24$ разных комплекта. Четырёхзначный ПИН-код из цифр от 0 до 9 с разрешёнными повторениями имеет $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ вариантов. Все формулы этой статьи — сокращения такого умножения: если задача кажется странной, возврат к поэтапному подсчёту всегда надёжен.

Факториалы

Чтобы поставить $n$ различных предметов в ряд, есть $n$ вариантов для первого места, $n - 1$ для второго и так далее до 1. Это произведение называется факториалом $n$:

Так, $5! = 120$: пять книг можно расставить на полке 120 разными способами. По определению $0! = 1$, что сохраняет согласованность формул ниже: есть ровно один способ упорядочить «ничего». Факториалы растут головокружительно быстро: $10! = 3{,}628{,}800$, а у перетасованной колоды карт $52!$ возможных порядков — это число из 68 цифр.

Перестановки и размещения: порядок важен

Размещение — это упорядоченная последовательность из $r$ предметов, выбранных из $n$ различных предметов. Поскольку порядок важен, «первый — второй — третий» отличается от «третий — второй — первый». Число размещений равно

Рассадка людей за круглым столом — особый случай. Если каждый пересядет на один стул дальше, получится та же рассадка, поэтому $n$ человек можно рассадить $(n-1)!$ различными способами. У шести человек за круглым столом $5! = 120$ рассадок, а не 720. Это называется круговой перестановкой.

Сочетания: порядок не важен

Сочетание — это выборка, в которой важно лишь то, какие элементы выбраны. Если выбрать в комиссию Анну, Бориса и Клару, получится одна и та же комиссия, в каком бы порядке их ни выбирали. Каждой группе из $r$ предметов соответствует $r!$ размещений, поэтому делим на это число:

Сочетания симметричны: $\binom{n}{r} = \binom{n}{n-r}$, потому что выбрать 3 человек, которые войдут, — то же самое, что выбрать 5, которые останутся за бортом. Это также числа треугольника Паскаля и коэффициенты при раскрытии бинома $(a + b)^n$.

Как понять, что нужно

Задайте один вопрос: если поменять местами два выбранных элемента, получится ли другой результат? Если да, порядок важен и нужны размещения. Если нет, берите сочетания.

• Места в соревновании, рейтинги, ПИН-коды, рассадки и расписания: размещения.
• Команды, комиссии, карточные руки, лотерейные билеты и начинки пиццы: сочетания.
• Должности внутри группы, например председатель и казначей, делают порядок важным, даже если люди выбираются из одной группы.

Быстрая проверка: число размещений всегда в $r!$ раз больше числа сочетаний. Если ваши два результата не удовлетворяют этому соотношению, один из них неверен.

Подсчёт с повторениями и повторяющимися буквами

Если элементы могут повторяться, формулы меняются. Упорядоченных выборок с повторениями $n^r$, как в примере с ПИН-кодом. Неупорядоченных выборок с повторениями, например 3 шарика мороженого из 5 вкусов, когда вкусы могут повторяться, будет

Расстановка букв с повторениями требует ещё одной поправки: нужно делить на факториал каждого числа повторений, потому что перестановка одинаковых букв ничего не меняет. Английское написание названия реки Миссисипи состоит из 11 букв, среди которых 4 буквы I, 4 буквы S и 2 буквы P: значит, у него $\frac{11!}{4!\,4!\,2!} = 34{,}650$ различных анаграмм.

Подсчёт для вычисления вероятностей

Если исходы равновозможны, вероятность — это число благоприятных исходов, делённое на число всех возможных, поэтому основную работу выполняют размещения и сочетания. Основу этого отношения объясняют основы теории вероятностей.

Карточные игры дают ещё больше упражнений. Существует $\binom{52}{5} = 2{,}598{,}960$ возможных раскладов из пяти карт. Расклад со всеми четырьмя тузами требует лишь ещё одной карты, выбранной из оставшихся 48, поэтому вероятность равна $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$.

Типичные ошибки

• Использовать размещения для команды или комиссии, что завышает подсчёт в $r!$ раз.
• Забывать, что $0! = 1$, из-за чего ломаются формулы вроде $\binom{n}{n}$.
• Не учитывать одинаковые элементы, например в анаграммах с повторяющимися буквами.
• Перемножать зависимые этапы, не корректируя последующие количества.

Калькулятор перестановок и сочетаний вычисляет ${}_nP_r$ и ${}_nC_r$ со всеми шагами через факториалы, а калькулятор вероятностей превращает эти количества в вероятности.

Треугольник Паскаля и подмножества

Каждое число в треугольнике Паскаля равно сумме двух чисел прямо над ним, а строка $n$ содержит значения $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Строка 4 — это 1, 4, 6, 4, 1, ровно коэффициенты $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$. Правило построения треугольника само является результатом подсчёта:

Чтобы понять почему, зафиксируйте один элемент. Любая выборка из $r$ элементов либо содержит его, и тогда остаётся выбрать $r - 1$ элементов из оставшихся $n - 1$, либо не содержит, и тогда все $r$ элементов выбираются из оставшихся $n - 1$. Сумма всей строки равна $2^n$ — общему числу подмножеств множества из $n$ элементов, ведь каждый элемент либо входит, либо нет. Поэтому пиццерия с 8 начинками может приготовить $2^8 = 256$ разных пицц, считая пиццу совсем без начинки.

Упражнения

1. Сколькими способами можно поставить на полку 4 книги, выбранные из 7 разных? Решение: ${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$.
2. Сколькими способами можно выбрать 4 начинки из 10? Решение: $\binom{10}{4} = 210$.
3. Сколько различных анаграмм у слова АНАНАС? Решение: $\frac{6!}{3!\,2!} = 60$.
4. Сколько пятибуквенных кодов можно составить из 26 букв, если повторения разрешены? Решение: $26^5 = 11{,}881{,}376$.

Частые вопросы