Элементы комбинаторики

Два основных правила комбинаторики позволяют посчитать число вариантов, не выписывая их по отдельности.

Пример: в меню $3$ вида супа и $4$ вида салата. Заказать одно блюдо — суп или салат — можно $3+4=7$ способами.

Пример: выбрать суп ($3$ варианта) и салат ($4$ варианта) на обед можно $3\cdot 4=12$ способами.

Обоснование правила произведения. Представь таблицу: строки — это $m$ вариантов первого действия, столбцы — $n$ вариантов второго. Каждой паре «строка, столбец» соответствует ровно одна клетка, а всего клеток $m\cdot n$. Правило распространяется и на большее число действий: для трёх шагов получится $m\cdot n\cdot p$ и так далее.

Как отличить: союз «или» подсказывает сложение, союз «и» (последовательные шаги) — умножение.

Во многих формулах комбинаторики встречается особое произведение — факториал.

Факториалом натурального числа $n$ называют произведение всех натуральных чисел от $1$ до $n$:

$n!=1\cdot 2\cdot 3\cdot \dots \cdot n$.

Читается «эн факториал». Несколько значений:

• $1!=1$;
• $2!=1\cdot 2=2$;
• $3!=1\cdot 2\cdot 3=6$;
• $4!=1\cdot 2\cdot 3\cdot 4=24$;
• $5!=120$.

Особый случай. По определению $0!=1$. Это соглашение нужно, чтобы формулы размещений и сочетаний работали и в крайних случаях.

Полезное свойство. Факториал удобно «раскрывать» через предыдущий: $n!=n\cdot (n-1)!$. Например, $6!=6\cdot 5!=6\cdot 120=720$. Это помогает сокращать дроби: $\frac{7!}{5!}=\frac{7\cdot 6\cdot 5!}{5!}=7\cdot 6=42$ — не нужно считать факториалы полностью.

Факториал растёт очень быстро: $10!=3628800$, поэтому в задачах его почти всегда сокращают, а не вычисляют целиком.

Перестановка из $n$ элементов — это любое упорядоченное расположение всех этих элементов в ряд. Перестановки отличаются друг от друга только порядком элементов (сами элементы одни и те же).

Число всех перестановок из $n$ элементов обозначают $P_n$ и вычисляют по формуле:

$P_n=n!$

Откуда формула. На первое место можно поставить любой из $n$ элементов. После этого на второе место остаётся $n-1$ элемент, на третье — $n-2$, и так далее, на последнее место — единственный оставшийся. По правилу произведения получаем $n\cdot (n-1)\cdot (n-2)\cdot \dots \cdot 1=n!$.

Пример. Сколькими способами можно расставить на полке $4$ разные книги? $P_4=4!=24$ способа.

Пример. Сколько различных «слов» (наборов букв) можно составить, переставляя буквы слова МИР? Все три буквы разные, значит $P_3=3!=6$.

Ключевой признак перестановки: используются все элементы и важен их порядок.

Размещение из $n$ элементов по $k$ — это упорядоченный выбор $k$ элементов из $n$ различных (без повторений). Два размещения считаются разными, если они отличаются либо составом, либо порядком элементов.

Число размещений обозначают $A_n^k$ и вычисляют по формуле:

$A_n^k=\frac{n!}{(n-k)!}=n\cdot (n-1)\cdot \dots \cdot (n-k+1)$.

В правой части — произведение ровно $k$ убывающих множителей, начиная с $n$.

Откуда формула. На первое место можно выбрать любой из $n$ элементов, на второе — $n-1$, и так $k$ раз. По правилу произведения это и даёт $n\cdot (n-1)\cdot \dots \cdot (n-k+1)$, что равно $\frac{n!}{(n-k)!}$.

Пример. Сколько двузначных «чисел» без повторений можно составить из цифр $\{1,2,3,4,5\}$? Порядок важен ($12$ и $21$ — разные), берём $2$ из $5$: $A_5^2=\frac{5!}{3!}=\frac{120}{6}=20$.

Связь с перестановками: если $k=n$, то размещение становится перестановкой: $A_n^n=\frac{n!}{0!}=n!=P_n$.

Ключевой признак размещения: выбираем часть элементов и порядок важен.

Сочетание из $n$ элементов по $k$ — это неупорядоченный выбор $k$ элементов из $n$ различных (без повторений). Два сочетания различны, только если различен их состав; порядок роли не играет.

Число сочетаний обозначают $C_n^k$ и вычисляют по формуле:

$C_n^k=\frac{n!}{k!(n-k)!}$.

Связь с размещениями. Каждое сочетание из $k$ элементов можно упорядочить $k!$ способами, и все эти упорядочения дают разные размещения. Поэтому $A_n^k=C_n^k\cdot k!$, откуда $C_n^k=\frac{A_n^k}{k!}$. Деление на $k!$ как раз «убирает» порядок.

Пример. Сколькими способами выбрать $2$ дежурных из $5$ учеников? Порядок не важен, поэтому $C_5^2=\frac{5!}{2!3!}=\frac{120}{2\cdot 6}=10$.

Ключевой признак сочетания: выбираем часть элементов и порядок не важен.

Это самый важный навык всей темы. И размещения, и сочетания — это выбор $k$ элементов из $n$. Разница только в одном: важен ли порядок выбранных элементов.

Главный приём — задай себе вопрос: «Если я переставлю выбранные элементы местами, получится ли другой вариант?»

• Если да, другой → порядок важен → размещение $A_n^k$.
• Если нет, тот же самый → порядок не важен → сочетание $C_n^k$.

Подсказки по словам в условии:

• Размещение (порядок важен): «по местам», «призовые места», «с распределением ролей», «пароль», «расписание», «кто первый, кто второй», «капитан и его заместитель».
• Сочетание (порядок не важен): «выбрать группу», «команда без ролей», «делегация», «букет из цветов», «горсть конфет», «подмножество».

Сравним на одном примере. Из $5$ спортсменов:

• распределить золото, серебро, бронзу — порядок важен, ведь $1$-е и $2$-е места различимы → размещение $A_5^3=60$;
• выбрать $3$ человек в сборную (без мест) — порядок не важен → сочетание $C_5^3=10$.

Заметь: размещений всегда больше (или столько же), потому что каждое сочетание порождает $k!$ размещений: $A_n^k=C_n^k\cdot k!$.

Краткая схема выбора формулы:

• Берём ВСЕ элементы и важен порядок → перестановка $P_n$.
• Берём ЧАСТЬ и важен порядок → размещение $A_n^k$.
• Берём ЧАСТЬ и порядок НЕ важен → сочетание $C_n^k$.