Перестановки и Сочетания

Подсчёт Расположений и Выборов из Группы

Перестановка (nPr) подсчитывает, сколькими способами можно расположить r элементов из n, где порядок важен, а сочетание (nCr) подсчитывает, сколькими способами можно выбрать r элементов из n, где порядок не важен. Введите общее количество элементов (n) и сколько вы выбираете (r), и этот калькулятор найдёт оба связанных ответа сразу.

Формулы

• Перестановки: $P(\vA{n}, \vB{r}) = \frac{\vA{n}!}{(\vA{n} - \vB{r})!}$ — эквивалентно, произведение $\vB{r}$ убывающих чисел, начиная с $\vA{n}$: $\vA{n} \times (\vA{n}-1) \times \cdots \times (\vA{n}-\vB{r}+1)$.
• Сочетания: $C(\vA{n}, \vB{r}) = \frac{P(\vA{n}, \vB{r})}{\vB{r}!}$ — то же количество перестановок, делённое на $\vB{r}!$ способов, которыми те же $\vB{r}$ элементов сами могли бы быть переупорядочены (поскольку для сочетания порядок не важен).

Пример Расчёта

Выбор 3 элементов из группы из 10, где порядок важен (перестановки):

$$P(10,3) = 10 \times 9 \times 8 = 720$$

Тот же выбор, где порядок НЕ важен (сочетания):

$$C(10,3) = 720 \div 3! = 720 \div 6 = 120$$

Проверка на Реальном Примере

Шансы угадать все 6 чисел в лотерейном розыгрыше 6 из 49 составляют 1 к C(49,6) — ровно 13 983 816, — поскольку порядок, в котором выпадают числа, не влияет на то, выиграли ли вы.

Ключевые Факторы, Которые Следует Учитывать

• Важен ли порядок — это единственный вопрос, который определяет, какая формула применяется. Расстановка призёров на подиуме (важно, кто на 1-м, 2-м, 3-м месте) — это задача на перестановки, тогда как выбор, какие 3 человека войдут в комитет (без ранжирования) — это задача на сочетания — правильное определение этого различия является самым частым источником ошибок при применении этих формул.
• Сочетания всегда дают равное или меньшее число, чем перестановки, для тех же n и r. Поскольку сочетание объединяет каждый возможный порядок тех же r элементов в одно число, C(n,r) всегда равно P(n,r), делённому на r! — эти два значения совпадают в точности только когда r равно 0 или 1, поскольку существует только один способ расположить 0 или 1 элемент независимо от порядка.
• И количество перестановок, и количество сочетаний растут чрезвычайно быстро с увеличением n и r. Этот взрывной рост (называемый комбинаторным взрывом) — именно то, почему шансы в лотереях становятся астрономически малыми при лишь скромном увеличении количества чисел, из которых проводится розыгрыш — переход от лотереи 6 из 49 к лотерее 6 из 59, например, заметно ухудшает шансы, несмотря на то что пул увеличивается всего на 10 чисел.
• Эти формулы предполагают, что каждый элемент уникален и ни один не может быть выбран более одного раза. Сценарий, допускающий повторный выбор (например, 4-значный PIN-код, где цифры могут повторяться), использует совершенно другую формулу подсчёта — всегда уточняйте, допускается ли повторение, прежде чем применять здесь стандартные формулы nPr/nCr.

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

• Использование числа перестановок, когда порядок на самом деле не важен, или наоборот. Это самая распространённая ошибка — прежде чем выбирать формулу, всегда сначала спрашивайте, будет ли перестановка местами двух выбранных элементов считаться другим результатом, а не угадывайте по формулировке задачи.
• Забывание, что сочетания никогда не превышают перестановки для тех же n и r. Если число сочетаний оказывается больше соответствующего числа перестановок при тех же входных данных, значит, что-то было введено неверно — сочетания делят число перестановок, уменьшая его, но никогда не увеличивают.
• Применение этих формул к ситуации, допускающей повторный выбор. Обе формулы предполагают, что каждый элемент можно выбрать не более одного раза — задача, допускающая повторения (например, генерация 4-значного PIN-кода), требует совершенно другого подхода к подсчёту, а не nPr или nCr.

Полезно Знать

• Хотите фактически вычислить вероятность конкретного исхода, а не просто подсчитать возможности? Калькулятор Вероятности превращает число сочетаний или перестановок в реальную вероятность.
• Работаете с полным набором данных, а не просто подсчитываете расположения? Калькулятор Статистики вычисляет среднее, стандартное отклонение и другие сводные показатели по списку чисел.
• Нужно упростить отношение или найти общий знаменатель как часть смежной комбинаторной задачи? Калькулятор НОД и НОК находит наибольший общий делитель и наименьшее общее кратное набора чисел.