Как выбрать формулу: порядок и повторения
Применяются четыре разные формулы подсчёта в зависимости от двух независимых вопросов: важен ли порядок и разрешены ли повторения?
| Важен ли порядок? | Разрешены ли повторения? | Формула | Пример ситуации |
|---|---|---|---|
| Да | Нет | nPr = n! ÷ (n − r)! | Распределение 1-го, 2-го и 3-го мест между 7 бегунами |
| Да | Да | nʳ | Составление трёхзначного PIN-кода из цифр 0–6, повторы разрешены |
| Нет | Нет | nCr = n! ÷ (r!(n−r)!) | Выбор комиссии из трёх человек среди 7 человек |
| Нет | Да | C(n+r−1, r) | Выбор 3 шариков мороженого из 7 вкусов, повторы разрешены |
- При одних и тех же n и r значение nCr всегда не превышает nPr (точнее, nCr = nPr ÷ r!), поскольку сочетания сводят каждую группу из r! упорядочиваний одних и тех же элементов к одному варианту.
- При r = 0 и nPr, и nCr по соглашению равны 1: существует ровно один способ не выбрать ни одного элемента (пустая выборка).
- При r = n (без повторений) nPr = n!, а nCr = 1: «выбрать» все n элементов как неупорядоченный набор можно единственным способом, но расставить их по порядку — n! способами.
Что такое размещения и сочетания?
Размещение — это расстановка элементов, в которой важен порядок. Число размещений r элементов, выбранных из набора в n различных элементов (без повторений), обозначается nPr и считает варианты вида «первое место, второе место, третье место», где перестановка двух выбранных элементов даёт другой, отличный исход.
Сочетание — это выборка элементов, в которой порядок не важен. Число сочетаний r элементов из n различных обозначается nCr (по-английски «n choose r», биномиальный коэффициент) и считает группы вроде состава комиссии или карточной руки, где тот же набор элементов в другом порядке считается тем же исходом.
Ключевой вопрос для различения: меняется ли результат, если переставить те же выбранные элементы? Если да (например, вручение золотой, серебряной и бронзовой медалей или расстановка книг на полке) — берите размещения. Если нет (например, выбор комиссии из трёх человек или сдача карточной руки) — берите сочетания. Калькулятор также выводит варианты «с повторениями», которые нужны, когда один и тот же элемент можно выбрать несколько раз (например, цифры PIN-кода или шарики мороженого, если вкусы могут повторяться).
Как пользоваться калькулятором размещений и сочетаний
- Введите n — общее число различных элементов, из которых делается выбор.
- Введите r — число выбираемых или расставляемых элементов. r должно быть не больше n: если r превышает n, калькулятор не выводит никаких результатов, включая варианты с повторениями.
- Смотрите размещения (nPr), если порядок выбора важен и повторения запрещены, или сочетания (nCr), если порядок не важен и повторения запрещены.
- Если один и тот же элемент можно выбирать несколько раз, пользуйтесь результатами «с повторениями», а не обычными значениями nPr и nCr.
Формулы размещений и сочетаний
Число размещений r элементов из n без повторений равно nPr = n! ÷ (n − r)!, что равносильно произведению r последовательно убывающих целых чисел начиная с n. Разбор примера при n = 7, r = 3: 7P3 = 7 × 6 × 5 = 210 — столькими способами можно распределить различные первое, второе и третье места между 7 участниками.
Число сочетаний r элементов из n без повторений равно nCr = n! ÷ (r! × (n − r)!) = nPr ÷ r!. Деление убирает r! способов упорядочить каждую выбранную группу, поскольку сочетания порядок не различают. Разбор примера при n = 7, r = 3: 7C3 = 210 ÷ 3! = 210 ÷ 6 = 35 — столько различных комиссий из трёх человек можно составить из 7 человек.
Число размещений с повторениями (каждую из r позиций независимо занимает любой из n элементов) равно просто nʳ. При n = 7, r = 3: 7³ = 343 — например, столько различных трёхзначных кодов можно составить из цифр 0–6, если повторы разрешены. Сочетания с повторениями считаются по формуле «шаров и перегородок»: C(n + r − 1, r). При n = 7, r = 3: C(9, 3) = 84 — например, столькими способами можно выбрать 3 шарика мороженого из 7 вкусов, если вкусы могут повторяться, а порядок не важен.
Типичные ошибки
- Применять формулу размещений там, где порядок на самом деле не важен (или наоборот): прежде чем выбирать формулу, проверьте, меняется ли исход при перестановке двух выбранных элементов.
- Забывать проверить, разрешены ли повторения: «составить PIN-код» (цифры могут повторяться) требует другой формулы, чем «сдать карты из колоды» (без повторений, карты в колоду не возвращаются).
- Применять nPr или nCr при r больше n, когда повторения запрещены: это не определено, ведь нельзя выбрать больше различных элементов, чем есть в наборе, не повторив ни одного.
- Путать «сочетания с повторениями» (формула шаров и перегородок) с обычным nCr: они дают совершенно разные результаты и относятся к разным ситуациям (повторы разрешены или нет).
Часто задаваемые вопросы
Чем размещение отличается от сочетания?
Размещение считает расстановки, где важен порядок (nPr = n! ÷ (n−r)!) — например, распределение 1-го, 2-го и 3-го мест. Сочетание считает выборки, где порядок не важен (nCr = n! ÷ (r!(n−r)!)) — например, выбор комиссии. При n = 7 и r = 3: 7P3 = 210 (с учётом порядка), но 7C3 = 35 (без учёта порядка), потому что каждую группу из 3 человек можно упорядочить 3! = 6 разными способами, и 210 ÷ 6 = 35.
Как вычислить nCr (число сочетаний из n по r)?
По формуле nCr = n! ÷ (r! × (n − r)!). При n = 7, r = 3: 7C3 = 7! ÷ (3! × 4!) = 5040 ÷ (6 × 24) = 5040 ÷ 144 = 35. Можно и иначе: сначала вычислить nPr (7 × 6 × 5 = 210) и разделить на r! (3! = 6): 210 ÷ 6 = 35.
Как вычислить nPr?
По формуле nPr = n! ÷ (n − r)!, которая сводится к произведению r последовательно убывающих целых чисел начиная с n. При n = 7, r = 3: 7P3 = 7 × 6 × 5 = 210.
Когда в задаче на размещения или сочетания нужно разрешать повторения?
Разрешайте повторения, если один и тот же элемент может попасть в исход несколько раз — например, цифры в PIN-коде или вкусы мороженого, когда покупатель берёт один и тот же вкус для нескольких шариков. Не разрешайте повторения, если каждый элемент используется только один раз — например, при сдаче различных игральных карт или назначении разных людей на разные должности.
Чему равно nPr при r = n?
При r = n (расстановка всех n элементов без повторений) nPr сводится к n! ÷ (n − n)! = n! ÷ 0! = n! ÷ 1 = n!. Это общее число способов расставить все n различных элементов в ряд — например, 5 элементов можно полностью упорядочить 5! = 120 способами.
Что означает метод «шаров и перегородок» для сочетаний с повторениями?
«Шары и перегородки» — стандартный комбинаторный приём для подсчёта сочетаний с повторениями, дающий формулу C(n + r − 1, r). Идея в том, чтобы изобразить r выбранных элементов «шарами», разделёнными «перегородками», которые отмечают границы между n категориями, и подсчитать число расстановок шаров и перегородок. При n = 7, r = 3: C(9, 3) = 84.
Источники
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018. (Permutations, combinations, and the stars-and-bars method.)
- NIST Digital Library of Mathematical Functions (DLMF), §26.1–26.3 Combinatorial Analysis. dlmf.nist.gov.
- Feller W. An Introduction to Probability Theory and Its Applications, Vol. 1. 3rd ed. Wiley, 1968. (Classic treatment of permutations and combinations.)