Перестановки, размещения, сочетания: формулы и задачи

Сколько существует четырёхзначных PIN-кодов? А паролей из 8 букв? Сколькими способами можно раздать 5 подарков пятерым детям? Комбинаторика отвечает на такие вопросы формулами — и в отличие от многих разделов математики, её результаты нужны постоянно: теория вероятностей, алгоритмы, оценка перебора, дизайн экспериментов. Хорошая новость: весь предмет держится на двух правилах и трёх формулах, которые мы сейчас и разберём.

Два правила, из которых растёт всё#

Правило умножения: если первое действие можно сделать $m$ способами, а второе — $n$ способами независимо от первого, то пара «первое и второе» делается $m\cdot n$ способами. Гардероб: 3 рубашки и 4 брюки дают $3\cdot 4=12$ комплектов. PIN-код: 4 позиции, на каждой 10 цифр — $10^4=10000$ вариантов, включая «0000».

Правило сложения: если выбор распадается на взаимоисключающие варианты, способы складываются. В буфете 5 пирожков и 3 булочки — выбрать одно изделие можно $5+3=8$ способами. Главный навык — чувствовать границу: действия происходят последовательно — умножаем, варианты взаимоисключающие — складываем. Ошибка «всегда умножаю» или «всегда складываю» стоит половины задачника.

Перестановки: расставляем всё по местам#

Перестановки — упорядочивания всех элементов множества. Сколькими способами можно расставить 4 книги на полке? На первое место претендуют 4 книги, на второе — 3 оставшиеся, дальше 2 и 1: $4\cdot 3\cdot 2\cdot 1=24$. Это произведение называется факториалом: $n!=1\cdot 2\cdot \cdots \cdot n$, и число перестановок из $n$ элементов равно $n!$.

Факториал растёт пугающе быстро: $5!=120$, $10!=3628800$, $20!\approx 2,4\cdot 10^{18}$ — больше, чем секунд в жизни Вселенной. Отсюда, кстати, следует важный вывод для программистов: полный перебор перестановок — занятие для $n$ до десяти, дальше нужны алгоритмы поумнее.

Перестановки с повторениями нужны, когда элементы не все различны. Слово МАТЕМАТИКА: 10 букв, но М встречается дважды, А — трижды, Т — дважды. Если бы все буквы были различны, перестановок было бы $10!$; перестановки одинаковых букв не создают новых слов, поэтому делим на их факториалы:

Размещения: выбираем и важно, кто первый#

Размещения из $n$ по $k$ — упорядоченные выборки $k$ элементов из $n$ различных: порядок важен. Сколькими способами из 10 участников выбрать золотого, серебряного и бронзового призёра? На золото 10 кандидатов, на серебро 9, на бронзу 8: $10\cdot 9\cdot 8=720$.

Числовой прогон: $A_{10}^3=\frac{10!}{7!}=10\cdot 9\cdot 8=720$. Здесь важно понимать смысл формулы, а не только буквы: в знаменателе сокращаются те $n-k$ элементов, которые в выборку не попали. Частный случай — размещения с повторениями: если элементы после выбора возвращаются, то каждая из $k$ позиций имеет $n$ вариантов, и ответ $n^k$. Тот же PIN-код: $10^4$.

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

Сочетания из $n$ по $k$ — выборки $k$ элементов из $n$, где порядок не важен. Из тех же 10 участников выбрать делегацию из трёх человек (без должностей) — это уже сочетание. Каждая неупорядоченная тройка порождает $3!=6$ упорядоченных, поэтому делим размещения на $k!$:

Считаем: $C_{10}^3=\frac{10\cdot 9\cdot 8}{3!}=\frac{720}{6}=120$. В шесть раз меньше, чем размещений, — и это чувствительная разница. Ещё одно свойство, которое часто экономит вычисления: $C_n^k=C_n^{n-k}$ (выбрать, кого взять, — то же, что выбрать, кого оставить). Отсюда $C_{100}^{98}=C_{100}^2=\frac{100\cdot 99}{2}=4950$ — без единого большого факториала.

Проверьте БАНАН сами: 5 букв, из них по два раза встречаются А и Н. $\frac{5!}{2!\cdot 2!}=\frac{120}{4}=30$. И ещё один практический приём из примера с экзаменом: $C_8^2=\frac{8\cdot 7}{2}=28$ — верхнюю часть считайте сразу произведением, а не через огромные факториалы.

Разбор типовой задачи по шагам#

Треугольник Паскаля и бином Ньютона#

Сочетания устроены рекурсивно. Возьмём конкретный элемент: либо он попал в выборку, либо нет. Первый случай: выбираем оставшиеся $k-1$ из $n-1$. Второй: $k$ из $n-1$. Отсюда правило Паскаля:

По краям треугольника стоят единицы ($C_n^0=C_n^n=1$), а каждое внутреннее число — сумма двух верхних: 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1… Числа в $n$-й строке — это коэффициенты разложения $n$-й степени суммы:

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

Три ошибки, которые кочуют по тетрадям#

1. Перепутать сложение с умножением. «Сложить» нужно, когда случаи не пересекаются; «умножить» — когда выбор идёт по этапам. Вопрос к себе: события происходят одновременно/последовательно (умножить) или это альтернативы (сложить)?
2. Не заметить порядок. Если в задаче есть должности, места, номера, «первый/второй» — это размещения или перестановки. Если просто «выбрать группу людей» — сочетания.
3. Делить на $k!$ там, где порядок важен, или наоборот. Проверка соотношением $A_n^k=C_n^k\cdot k!$: размещения всегда больше сочетаний.

Отработать выбор формулы до рефлекса поможет тренажёр комбинаторики: генератор выдаёт случайные задачи с полным решением, и через десяток задач глаз сам различает тип. А если вы уже считаете $C_n^k$ во сне — время применять их в задачах на вероятность, где классическое определение вероятности — это отношение двух комбинаторных чисел.

1. 1
   Условие: шесть человек встают в очередь; сколькими способами — при условии, что Аня стоит где-то впереди Бори?
2. 2
   Без условия: $6!=720$ перестановок.
3. 3
   Ключевое наблюдение: в каждой паре зеркальных перестановок (поменяли Аню и Борю местами) ровно одна удовлетворяет условию.
4. 4
   Значит, ответ — половина: $360$. Никаких сложных подсчётов, одна симметрия.

Родственный приём — «склейка». Пять книг ставят на полку, но две определённые должны стоять рядом. Склейте их в один блок: объектов стало четыре, их перестановок $4!=24$; внутри блока две книги меняются местами — ещё $2!=2$. Итого $24\cdot 2=48$ расстановок. Приём работает для любого условия «вместе/рядом», а зеркальная задача «не рядом» решается вычитанием: $120-48=72$. Когда перебор случаев громоздкий, выручает лемма Бернсайда — подсчёт орбит перестановок.

Три формулы легко перепутать: где порядок важен, а где нет. Счётчик ниже показывает разницу числами при одинаковых $n$ и $k$ — сравнение запоминается мгновенно.