Сочетания и перестановки: в чём разница

Сочетания и перестановки - две базовые конструкции комбинаторики, и большая часть ошибок в задачах на подсчёт вариантов начинается с того, что их путают. Формулы похожи, обе выражаются через факториалы, а вся разница спрятана в одном вопросе: важен ли порядок, в котором мы берём элементы. Если важен, работают перестановки и размещения; если нет - сочетания, и ответы расходятся ровно в $k!$ раз. Ниже разберём три формулы, их связь и способ выбрать нужную за три вопроса. А калькулятор сразу покажет, насколько сильно расходятся ответы при ваших $n$ и $k$.

Порядок важен или нет: главный вопрос

Любая задача «сколькими способами» сводится к выбору подмножества элементов из данного множества, и различаются такие задачи только двумя признаками: берём ли мы все элементы или часть, и считаем ли разными выборки, отличающиеся лишь порядком.

Возьмём три буквы А, Б, В. Записи АБВ и БАВ состоят из одних и тех же букв, но как слова они разные - здесь порядок важен, и это перестановки. А если из тех же букв нужно выбрать две для набора магнитиков на холодильник, то наборы {А, Б} и {Б, А} - один и тот же набор: порядок не важен, это сочетание.

Чтобы вопрос «важен ли порядок» перестал быть интуитивным, полезно спрашивать иначе: изменится ли смысл ответа, если поменять местами два выбранных объекта. Медали чемпионата поменялись - результат другой. Состав делегации переставили - делегация та же.

Рассчитать для своей задачи

Перестановки: расставляем все элементы

Перестановка - это способ упорядочить все $n$ элементов множества. Число таких способов обозначают $P_n$:

$P_n = n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$

Формула выводится из правила произведения: на первое место можно поставить любой из $n$ элементов, на второе - любой из оставшихся $n-1$, и так до последнего места, где выбора уже нет. Перемножаем: $n(n-1)\cdots 2 \cdot 1$.

Типовая задача: сколькими способами расставить 5 книг на полке? Ответ $P_5 = 5! = 120$. Ещё пример: сколько шестизначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6 без повторов? Тоже $6! = 720$.

Факториал растёт стремительно: $10! = 3\,628\,800$, а $15!$ уже больше триллиона. Поэтому в задачах на перестановки почти никогда не просят перечислить варианты - только посчитать.

Отдельный случай - когда среди элементов есть одинаковые. Тогда прямой факториал завышает ответ, и нужна формула перестановок с повторениями: $n!$ делится на произведение факториалов кратностей.

Размещения: выбираем часть и расставляем

Размещение - это упорядоченная выборка $k$ элементов из $n$. Число размещений:

$A_n^k = \frac{n!}{(n-k)!} = n(n-1)(n-2)\cdots(n-k+1)$

В правой части ровно $k$ множителей, и считать удобнее именно так, без больших факториалов. Например, из 10 спортсменов распределить золото, серебро и бронзу можно $A_{10}^3 = 10 \cdot 9 \cdot 8 = 720$ способами: тут важно не только кто попал в тройку, но и какое место занял.

Перестановки - частный случай размещений, когда берут все элементы:

$A_n^n = \frac{n!}{0!} = n! = P_n$

Здесь работает соглашение $0! = 1$: единственный способ ничего не расставлять - это пустая расстановка.

Сочетания: выбираем часть без порядка

Сочетание - это неупорядоченная выборка $k$ элементов из $n$, то есть просто подмножество размера $k$. Число сочетаний, оно же биномиальный коэффициент:

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

Из тех же 10 спортсменов выбрать команду из трёх человек можно $C_{10}^3 = 120$ способами - в шесть раз меньше, чем распределить медали, потому что каждая тройка даёт $3! = 6$ разных распределений мест.

Полезные свойства, которые экономят время на контрольной:

• симметрия: $C_n^k = C_n^{n-k}$ (выбрать $k$ элементов - то же, что выбрать $n-k$ отбрасываемых);
• края: $C_n^0 = C_n^n = 1$, $C_n^1 = n$;
• сумма по всем размерам: $C_n^0 + C_n^1 + \ldots + C_n^n = 2^n$ - это все подмножества;
• рекуррентность Паскаля: $C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k}$.

Рассчитать для своей задачи

Как связаны три формулы

Все три конструкции - это одна формула, рассмотренная под разными углами. Ключевое соотношение:

$A_n^k = C_n^k \cdot k!$

Читается оно как двухшаговая процедура: сначала выбираем, какие именно $k$ элементов берём (это $C_n^k$ способов), потом расставляем выбранные по местам (это $k!$ способов). Отсюда сразу видно, почему упорядоченных выборок всегда больше или столько же, и во сколько раз именно.

Обратное чтение даёт удобный приём: если задача решена «с порядком», а порядок на самом деле не нужен, ответ достаточно поделить на $k!$. Именно так обычно избавляются от лишнего порядка в задачах про рукопожатия, диагонали многоугольника и выбор команды.

Рассчитать для своей задачи

Как выбрать формулу за три вопроса

1. Берём все элементы или часть? Все - перестановки $P_n = n!$. Часть - переходим к следующему вопросу.
2. Важен ли порядок внутри выборки? Да - размещения $A_n^k$. Нет - сочетания $C_n^k$.
3. Элементы могут повторяться? Если выбор идёт с возвращением и порядок важен, это размещения с повторениями: $\bar{A}_n^k = n^k$. Если повторы есть в исходном наборе одинаковых предметов - нужны перестановки с повторениями.

Третий вопрос забывают чаще всего, а он решающий в задачах про коды, пароли и номера: там цифры повторяются, и вместо $A_{10}^4 = 5040$ правильный ответ $10^4 = 10\,000$.

Разбор типовых задач

Комиссия и президиум. В группе 12 студентов. Сколькими способами выбрать: (а) комиссию из 3 человек; (б) председателя, секретаря и казначея? В пункте (а) роли не различаются, порядок не важен: $C_{12}^3 = 220$. В пункте (б) роли разные: $A_{12}^3 = 12 \cdot 11 \cdot 10 = 1320$. Отношение $1320 / 220 = 6 = 3!$ - ровно тот множитель из связи формул.

Рукопожатия. Каждый из 15 участников встречи пожал руку каждому по одному разу. Сколько было рукопожатий? Рукопожатие - неупорядоченная пара: $C_{15}^2 = \frac{15 \cdot 14}{2} = 105$. Если бы считали упорядоченные пары «кто кому», получили бы $A_{15}^2 = 210$, то есть каждое рукопожатие дважды.

Смешанная задача. В ящике 7 белых и 5 чёрных шаров; вынимают 4 шара. Сколько выборок содержат ровно 2 белых? Выбираем 2 белых из 7 и 2 чёрных из 5 независимо, затем перемножаем по правилу произведения: $C_7^2 \cdot C_5^2 = 21 \cdot 10 = 210$. Такие подсчёты - основа формулы вероятности через сочетания, где числитель и знаменатель одинаково собираются из биномиальных коэффициентов.

Слово из букв. Сколько различных «слов» получится из букв слова КНИГА? Все буквы разные, берём все: $P_5 = 120$. А если бы слово было КНИЖКА, повторяющаяся К заставила бы делить на $2!$.

Частые ошибки

• Считают порядок там, где его нет. Классика - команда, комиссия, набор блюд: если роли не названы, это сочетания, а не размещения. Признак ошибки: ответ кратен $k!$ и выглядит подозрительно большим.
• Путают, что стоит в знаменателе. В размещениях делят на $(n-k)!$, в сочетаниях - ещё и на $k!$. Проверка: подставьте $k = n$ и посмотрите, получается ли $n!$ и $1$ соответственно.
• Забывают про повторения. Задачи про пароли, номера и броски кубика почти всегда «с возвращением», и там работает $n^k$, а не $A_n^k$.
• Складывают вместо умножения. Если этапы выбора идут последовательно и независимо, результаты перемножаются; складываются только взаимоисключающие случаи.
• Раскрывают факториалы полностью. $A_{50}^3$ не требует $50!$: достаточно $50 \cdot 49 \cdot 48$. Прямой подсчёт больших факториалов приводит к арифметическим ошибкам и переполнению калькулятора.

FAQ

Чем сочетания отличаются от перестановок одной фразой? Перестановки упорядочивают все элементы, сочетания выбирают часть без учёта порядка. Промежуточный случай - размещения: выбираем часть и учитываем порядок.

Что больше: $C_n^k$ или $A_n^k$? Размещений всегда не меньше: $A_n^k = C_n^k \cdot k!$. Равенство достигается только при $k = 0$ или $k = 1$, когда переставлять нечего.

Почему $0! = 1$, а не $0$? Это соглашение, которое делает формулы согласованными: при $k = n$ размещения должны давать $n!$, а сочетания - единицу. Содержательно пустую выборку можно упорядочить ровно одним способом.

Коротко

Сочетания и перестановки различаются одним признаком - учитывается ли порядок. Перестановки расставляют все $n$ элементов: $P_n = n!$. Размещения выбирают $k$ из $n$ с учётом порядка: $A_n^k = n!/(n-k)!$. Сочетания выбирают $k$ из $n$ без порядка: $C_n^k = n!/(k!(n-k)!)$. Связывает их равенство $A_n^k = C_n^k \cdot k!$, а выбор формулы сводится к трём вопросам: берём всё или часть, важен ли порядок, возможны ли повторы.