Главный вопрос: имеет ли значение порядок?
И перестановки, и сочетания подсчитывают число способов выбрать r элементов из группы, состоящей из n различных элементов, но отвечают на два разных вопроса. Перестановка подсчитывает число способов выбрать и расположить r элементов, поэтому две выборки с одинаковыми элементами, но в разном порядке, считаются двумя отдельными исходами. Сочетание подсчитывает только число способов выбрать r элементов, поэтому две выборки с одинаковыми элементами считаются одним исходом независимо от порядка, в котором они были отобраны.
Простой способ определить, что применимо: представьте себе два варианта, использующие ровно одни и те же элементы, но перечисленные или расположенные по-разному. Если эти два варианта представляют собой действительно разные реальные результаты — разные рейтинги, разные пароли, разный порядок финиша в гонке, — порядок имеет значение, и правильным подсчётом будет перестановка. Если эти два варианта представляют собой один и тот же реальный результат — тот же комитет, ту же карточную руку, тот же набор лотерейных чисел, — порядок не имеет значения, и правильным подсчётом будет сочетание.
Формулы: nPr и nCr на проверенном примере
Число перестановок из r элементов, выбранных из n различных элементов, равно nPr = n! / (n − r)!, а число сочетаний равно nCr = n! / [r! (n − r)!] — формула сочетаний представляет собой формулу перестановок, делённую на r!, поскольку деление на r! убирает r! различных упорядочений внутри каждой группы одинаковых элементов, которые подсчёт перестановок рассматривает как разные.
Разобранный пример: выбор 3 элементов из группы из 7. Перестановки: 7P3 = 7! / (7−3)! = 7 × 6 × 5 = 210. Сочетания: 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35. Число сочетаний равно в точности числу перестановок, делённому на 3! = 6, что подтверждает соотношение nCr = nPr / r!.
| Величина | Формула | Значение при n=7, r=3 |
|---|---|---|
| Перестановки (порядок важен) | nPr = n! / (n − r)! | 7P3 = 7 × 6 × 5 = 210 |
| Сочетания (порядок не важен) | nCr = n! / [r!(n − r)!] | 7C3 = 210 / 3! = 35 |
С повторением и без повторения
Обе формулы выше предполагают, что каждый из n элементов может быть выбран не более одного раза — выборка без повторения. Когда элементы могут использоваться повторно (выборка с повторением, также называемая выборкой с возвращением), формулы подсчёта меняются. Перестановки с допустимым повторением просто возводят n в степень r, поскольку каждая из r позиций независимо имеет все n вариантов выбора вне зависимости от того, что было выбрано ранее: n^r.
Сочетания с допустимым повторением используют другую формулу, C(n + r − 1, r), которая подсчитывает число способов выбрать r элементов из n типов, когда повторы разрешены, а порядок по-прежнему не имеет значения, — этот случай требуется реже, но встречается, например, при выборе шариков мороженого из n вкусов, когда один и тот же вкус можно выбрать более одного раза.
| Случай | Формула | Типичный пример |
|---|---|---|
| Перестановки, без повторения | n! / (n − r)! | Определение 3 победителей из 7 финалистов |
| Перестановки, с повторением | n^r | 4-значный PIN-код, в котором цифры могут повторяться |
| Сочетания, без повторения | n! / [r!(n − r)!] | Выбор 6 чисел для лотерейного билета |
| Сочетания, с повторением | (n + r − 1)! / [r!(n − 1)!] | Выбор 3 шариков из 5 вкусов мороженого с допустимыми повторами |
Разобранные примеры: PIN-код и лотерейный билет
4-значный PIN-код, где каждая из 4 позиций может быть любой цифрой от 0 до 9, а цифры могут повторяться (обычное правило для банковских PIN-кодов), — это пример перестановок с повторением: порядок имеет значение (1234 и 4321 — разные PIN-коды), и повторение разрешено, что даёт 10^4 = 10 000 возможных PIN-кодов. Если бы повторяющиеся цифры были запрещены, число вариантов упало бы до значения перестановок без повторения, 10P4 = 10 × 9 × 8 × 7 = 5040 — меньше вариантов, поскольку каждая использованная цифра убирает один вариант для оставшихся позиций.
Классический лотерейный формат, в котором из пула 49 чисел вытягивается 6 чисел, ни одно число не повторяется, а порядок вытягивания не влияет на выигрыш билета, — это пример сочетаний без повторения: C(49, 6) = 49! / (6! × 43!) = 13 983 816. Эта большая величина как раз и объясняет, почему такие лотерейные форматы описываются как игры с очень низкими шансами, — число сочетаний растёт очень быстро по мере роста n относительно r, поскольку оно подсчитывает неупорядоченные группы из большого пула, а не небольшой фиксированный набор расположений.
Быстрый способ запомнить, какую формулу использовать
И «перестановка», и «позиция» начинаются со звука «п», и полезный мнемонический приём — помнить, что перестановки заботятся о позиции: о том, где в последовательности находится каждый элемент. «Сочетание» описывает объединённую группу — например, содержимое сумки или состав комитета, — где имеет значение только принадлежность к группе, а не порядок, в котором её члены были добавлены.
Пароли, PIN-коды, места в рейтинге гонки и любые задачи о рассадке или расписании — это задачи на перестановки, поскольку изменение порядка меняет результат. Карточные руки, наборы лотерейных чисел, состав комитета и любой неупорядоченный выбор группы — это задачи на сочетания, поскольку значение имеют только сами члены группы, а не порядок, в котором они были выбраны.
Часто задаваемые вопросы
В чём разница между перестановкой и сочетанием?
Перестановка подсчитывает расположения, в которых порядок имеет значение, поэтому выбор тех же элементов в другом порядке считается другим исходом. Сочетание подсчитывает выборки, в которых порядок не имеет значения, поэтому те же элементы в любом порядке считаются одним исходом. Обе величины исходят из одной и той же группы из n элементов и предполагают выбор r из них, но число перестановок всегда больше или равно соответствующему числу сочетаний при одинаковых n и r.
Что такое 7P3 и как это вычислить?
7P3 равно 210 — числу способов выбрать и расположить 3 элемента из группы из 7 различных элементов, когда порядок имеет значение. Вычисляется как 7P3 = 7! / (7 − 3)! = 7 × 6 × 5 = 210, перемножая три наибольших множителя 7!, поскольку меньшие множители сокращаются с (7−3)! в знаменателе.
Что такое 7C3 и как это вычислить?
7C3 равно 35 — числу способов выбрать 3 элемента из группы из 7 различных элементов, когда порядок не имеет значения. Вычисляется как 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35 — это в точности число перестановок, 7P3 = 210, делённое на 3! (число способов переставить каждую группу из 3), поскольку сочетания объединяют все упорядочения одной и той же группы в один исход.
Почему в PIN-кодах используются перестановки, а в лотереях — сочетания?
PIN-код считает 1234 и 4321 разными кодами, поэтому порядок цифр меняет результат, — это сценарий перестановок с допустимым повторением для типичного 4-значного PIN-кода, что даёт 10^4 = 10 000 вариантов. Лотерейный билет выигрывает только на основании того, какие числа выпали, а не порядка, в котором они появились, поэтому два розыгрыша с одними и теми же числами в разном порядке — это один и тот же выигрышный исход, — это сценарий сочетаний: для формата 6 из 49 C(49,6) = 13 983 816 возможных наборов чисел.
Что означает «с повторением» в формуле перестановок или сочетаний?
Это означает, что элемент можно выбрать более одного раза в рамках одного исхода. Перестановки с допустимым повторением используют n^r (каждая из r позиций независимо имеет все n вариантов выбора), а сочетания с допустимым повторением используют (n + r − 1)! / [r!(n − 1)!]. Без повторения каждый элемент можно использовать не более одного раза, что и предполагают стандартные формулы nPr и nCr.
Источники
- NIST Digital Library of Mathematical Functions (DLMF), §26 Combinatorial Analysis. dlmf.nist.gov.
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018 (permutations, combinations, and counting with repetition).
- Ross SM. A First Course in Probability. Pearson (combinatorial counting methods).
- Weisstein EW. "Permutation" and "Combination." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.