Калькулятор перестановок

P(n, r) = n! / (n − r)! = nPr C(n, r) = n! / (r! (n − r)!) P(n, r) = C(n, r) · r!

n

Размер пула, из которого выбирают, — число различных доступных предметов, до 1000. Этот потолок ограничивает арифметику, а не саму идею: счёт растёт вместе с n, и после некоторой точки точное значение уже не помещается в диапазон целых, который эта страница представляет точно

r

Сколько предметов берётся. Пока повторы запрещены, оно не может превысить n, потому что различных предметов больше, чем их есть, взять нельзя; когда повторы разрешены, r может быть больше и ограничено лишь тем, какую степень страница ещё считает точно

n!

Факториал n: n, умноженное на все целые числа ниже него до единицы. Это счёт для случая, когда берут всё и по порядку, и именно его убирает деление на (n − r)!

P(n, r)

Число размещений: n вариантов на первую позицию, n − 1 на вторую и так далее для r позиций. Произведение n × (n − 1) × … × (n − r + 1) — это и есть записанное формулой n! / (n − r)!

C(n, r)

Счёт без учёта порядка, выводимый второй строкой. Он делит число размещений на r! — число способов упорядочить любой один выбранный набор, — и в этом вся разница между двумя строками

allowRepetition

В каком из двух режимов находится страница. Когда повторы разрешены, счёт становится n в степени r, потому что у каждого из r выборов снова весь пул в распоряжении; строка без учёта порядка переключается на счёт мультимножеств

Берите его, когда позиции различимы: призовые места в забеге, порядок первых трёх сданных карт, пароль, номерной знак или схема рассадки — любой список, где перестановка двух записей даёт другой результат. Строку сочетаний — или вторую страницу этой пары — берите тогда, когда результат есть множество, потому что тогда два расположения одних и тех же r предметов дают один ответ, и деление на r! и есть нужная поправка. Включайте повторы, когда предмет можно взять снова после того, как его взяли: у четырёхзначного PIN-кода 10⁴ вариантов, потому что каждая цифра берётся из полного набора десяти, а тираж лотереи различные шары из барабана не повторяет. И читайте вторую строку, даже если пришли за первой: два счёта вместе — самое ясное объяснение того, почему порядок вообще имеет значение, ведь они различаются одним множителем.

1. Десять предметов, три места, порядок учитывается

   1. Десять вариантов на первое место, девять остаётся на второе, восемь на третье
   2. Перемножим: 10 × 9 × 8 = 720 размещений
   3. Без учёта порядка делим на 3! = 6, получая 120 наборов
   4. 720 / 120 = 6, а это ровно 3!

   Две строки — вся суть этой страницы в одной строчке: одни и те же десять предметов и одни и те же три места дают 720, если порядок учитывается, и 120, если нет, а отношение между ними равно 3! — числу способов переставить три выбранных предмета. Всякий раз, когда перестановка и сочетание выглядят несогласованными, деление одного на другое и есть проверка: если отношение не равно факториалу, дело в постановке задачи, а не в арифметике.

2. Призовая тройка из восьми бегунов

   1. Восемь возможных победителей, семь возможных вторых, шесть возможных третьих
   2. 8 × 7 × 6 = 336 способов заполнить пьедестал
   3. Без учёта порядка одни и те же три человека образуют один набор, как их ни расставь: 336 / 6 = 56
   4. Обратный путь через умножение — 8!/(8−3)! = 40320/120 — даёт те же 336

   Это повседневная форма того же различия: результат забега есть перестановка, потому что серебро не равно золоту, а прошедшая отбор группа есть сочетание, потому что трое прошедших — одни и те же трое, кто бы ни бежал быстрее. Заметьте, что та же пара чисел появится на странице сочетаний с двумя строками наоборот, — это пара, работающая как задумано, а не дублирование.

3. Раздача пяти карт по порядку

   1. Пятьдесят два варианта на первую карту, пятьдесят один на вторую и так далее до сорока восьми на пятую
   2. 52 × 51 × 50 × 49 × 48 = 311 875 200 упорядоченных раздач
   3. Рука из пяти карт порядок не учитывает, поэтому делим на 5! = 120
   4. 311 875 200 / 120 = 2 598 960 — знакомое число пятикарточных покерных рук

   2 598 960 — то число, которое цитируют в каждой покерной вероятности, и поэтому именно здесь читатель может сверить страницу с тем, что видел в других местах. Это и самый наглядный случай, когда множитель упорядочивания огромен: раздача тех же пяти карт в другой последовательности — другая упорядоченная раздача, но та же рука, и множитель между счётами равен 120, а не 6. Оба счёта здесь точны, без округления.

4. Трёхзначные коды, где цифры могут повторяться

   1. Когда повторы разрешены, каждая из трёх позиций выбирается из всех десяти цифр независимо
   2. 10 × 10 × 10 = 1000 кодов
   3. Строка без учёта порядка — уже не 1000 / 6, потому что расположения кода вроде 777 не все различны
   4. Она становится счётом мультимножеств: C(10 + 3 − 1, 3) = C(12, 3) = 220

   Интересное число здесь — второе. У различных предметов счёт без учёта порядка есть просто число размещений, делённое на r!, но как только повторы разрешены, это деление исправляет слишком много — у 777 лишь одно различное расположение, а не шесть, — поэтому страница переключается на другую формулу, а не делит. 220 — это число трёхзначных мультимножеств из десяти цифр, и именно поэтому переключатель повторов меняет обе строки, а не только первую.

Две границы здесь соблюдаются, а не объясняются постфактум, и обе стоит знать до того, как числа удивят. Пока повторы запрещены, r не может превысить n: взять четыре предмета из пула в три различных — не маловероятный исход, а невыполнимая просьба, и страница говорит об этом, а не возвращает ноль. Размер пула ограничен 1000. Второй предел и есть тот, что действительно кусается на практике: число размещений — произведение, растущее чрезвычайно быстро, а страница сообщает точные целые, а не приближение в экспоненциальной записи. После точки, где истинное значение перестаёт представляться точно, она отказывается отвечать вместо того, чтобы напечатать целое с неверными последними цифрами, — правдоподобно выглядящее неверное число здесь куда хуже ясного отказа, потому что неверное число будет скопировано во всё, что от него зависит. Есть и меньший арифметический предел на ветви с повторами, где счёт является степенью и очень большие показатели переполняются так же. Два замечания о смысле. Ни одна из строк здесь не есть вероятность: обе — счёт равновероятных расположений, а превращение счёта в шанс означает деление на общее число возможностей, которое зависит от процесса, а не от пары чисел на этой странице. И таблицы факториалов, биномиальных коэффициентов или треугольника Паскаля здесь нет по причине, изложенной в пятом вопросе ниже.

Чем перестановка отличается от сочетания?

Перестановка считает расположения, а сочетание — наборы: поменяйте местами два выбранных предмета, и у перестановки получится другой результат, а у сочетания нет. Страница сообщает обе строки, чтобы соотношение было видно, а не заявлено: число размещений всегда больше, а деление его на факториал r даёт вторую строку. На практике спрашивать надо о том, несут ли позиции смысл. Если третье место отличается от второго, как в результате забега или в карте, сданной по порядку, нужен счёт размещений; если три выбранных предмета взаимозаменяемы, нужен счёт наборов.

Почему две строки различаются ровно в r факториал раз?

Потому что каждый набор из r выбранных предметов выстраивается в r! разных последовательностей, а счёт размещений считает каждую из этих последовательностей отдельным исходом. При r = 3 любые три предмета упорядочиваются шестью способами, поэтому одному набору соответствует шесть размещений, и число размещений в шесть раз больше числа наборов. Это и самый быстрый способ проверить расчёт: разделите две строки, и ответ должен быть факториалом. Если это не так, расхождение в постановке задачи, а не в арифметике, — чаще всего в размере пула или в режиме повторов, не соответствующем описанной ситуации.

Когда выбор одного и того же предмета дважды считается другим?

Ровно тогда, когда ситуация вообще позволяет взять его дважды, — это и есть переключатель повторов, и он меняет обе строки, а не только первую. Четырёхзначный PIN-код берёт каждую цифру заново из всех десяти, поэтому 0000 и любой другой повтор — обычные исходы, и счёт равен 10⁴; тираж лотереи вынимает шары из барабана, поэтому ни одно число не может появиться дважды, и счёт становится убывающим произведением. Когда повторы разрешены, счёт наборов уже не равен числу размещений, делённому на r!, потому что у выбора вроде 777 одно различное расположение, а не шесть, и для этой строки страница использует счёт мультимножеств.

Почему страница отказывается взять предметов больше, чем есть в пуле?

Пока повторы запрещены, r больше n описывает процедуру, которую нельзя выполнить: четвёртого различного предмета не существует, когда доступны только три. Страница сообщает о проблеме вместо того, чтобы вернуть ноль, потому что ноль в других ситуациях является законным счётом и был бы прочитан как ответ. Включите повторы — и та же просьба становится совершенно обычной: три предмета, взятые по пять с повторами, дают 3⁵ = 243 размещения, — и поэтому ограничение наложено на сочетание двух настроек, а не на r само по себе.

Почему на этой паре страниц нет треугольника Паскаля или таблицы факториалов?

Потому что таблица здесь не видела бы двух введённых вами чисел, а таблица, которую хотят видеть, — факториалы, биномиальные коэффициенты, строки треугольника Паскаля — это список для фиксированных малых значений. Поставьте её на страницу, и она отвечала бы на другой вопрос, нежели панель над ней, иногда заметно расходясь со строкой, на которую вы смотрите, а это хуже отсутствия таблицы. Панель и есть таблица: измените n, r или режим повторов — и обе строки пересчитаются. Эта пара страниц выносит тот же приговор, что и остальные счётные инструменты, вместо того чтобы одна страница давала таблицу, а другая нет: это ведь два направления одного и того же вопроса.

Почему для больших пулов ответ перестаёт работать?

Потому что число размещений — произведение длинных последовательностей целых чисел, и оно переходит наибольшее целое, которое эта страница представляет точно, куда раньше, чем большинство ожидает: факториал 19 уже за этой чертой, хотя его 18 цифр и не выглядят тревожно. После этой точки страница отказывается отвечать вместо того, чтобы напечатать число с неверными последними цифрами, а цифры и составляют всю ценность точного счёта: неверное целое выглядит совершенно обыкновенно и будет скопировано в любой зависящий от него расчёт. Потолок пула в 1000 — отдельная, более мягкая защита от той же тревоги: он останавливает ввод на размере, при котором арифметику ещё имеет смысл пробовать.

• Permutation — from Wolfram MathWorld (a rearrangement of the elements of an ordered list, and the count of them for a set of a given size) — Wolfram MathWorld
• Combination — from Wolfram MathWorld (the number of ways of picking unordered outcomes from a set, also called the binomial coefficient and read "n choose k") — Wolfram MathWorld
• 1.3.6.1. What is a Probability Distribution — e-Handbook of Statistical Methods (the frequency reading of probability, which is how a count of equally likely arrangements becomes a chance) — National Institute of Standards and Technology (NIST)