Калькулятор сочетаний

combinations C(n, r) = n! / (r!(n − r)!) · permutations P(n, r) = n! / (n − r)! · с повторениями: C = (n + r − 1)! / (r!(n − 1)!) и P = nʳ

n

Сколько всего разных предметов есть на выбор — размер пула, а не число выборов

r

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

allow repetition

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

C(n, r)

Число сочетаний, читаемое как nCr: способы выбрать r предметов, когда порядок выбора не учитывается, так что ABC и CBA считаются один раз

P(n, r)

Число перестановок: способы выбрать, а затем упорядочить r предметов, так что ABC и CBA — два разных результата. Оно всегда равно числу сочетаний, умноженному на r!

Берите его всюду, где вопрос на самом деле «сколько способов», — а так бывает в большинстве случаев, когда вероятность считают перебором, а не по формуле. Карточные руки, тиражи лотерей, выбор комитета и рассадка — всё это один и тот же расчёт, и единственное решение, которое нужно принять до него, — важен ли порядок: покерная рука — это сочетания, а пьедестал — перестановки. Переключатель повторений нужен там, где один и тот же выбор можно сделать дважды: три шарика мороженого из списка вкусов, где порядок по-прежнему не важен, но вкусы могут повториться, — это сочетания с повторениями, где порядок не важен, а повторы разрешены. Страница считает только числа, из которых строятся вероятности, и ничего больше.

1. Десять предметов, выбрать три: 120 сочетаний или 720 перестановок

   1. Без учёта порядка C(10,3) = 10! / (3! × 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 120
   2. С учётом порядка P(10,3) = 10 × 9 × 8 = 720
   3. Эти два числа отличаются в 3! = 6 раз, а 6 — это число способов упорядочить три выбранных предмета
   4. Проверка: 120 × 6 = 720

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

2. Те же десять и три, но с повторениями

   1. С повторениями и без учёта порядка C = (10 + 3 − 1)! / (3! × 9!) = C(12,3) = 220
   2. С повторениями и с учётом порядка P = 10³ = 1000
   3. Для числа сочетаний пул фактически становится больше — формула прибавляет к n величину r − 1, — тогда как число перестановок это просто по одному выбору на каждую позицию
   4. Проверка: 220 — это не 120, а 1000 — не 720: переключатель сдвинул обе строки

   Обе строки изменились, и в этом смысл переключателя, а не деталь его работы. Реализация, которая поправила бы только число сочетаний, напечатала бы 220 и 720 рядом, и оба числа выглядели бы правдоподобно, описывая при этом разные правила. Заметьте также, что число перестановок теперь степень, а не убывающее произведение: с повторениями на каждую из r позиций приходится n вариантов, поэтому произведение сворачивается в nʳ вместо того, чтобы уменьшаться на единицу каждый раз.

3. Покерная рука из пяти карт в колоде из 52

   1. Рука неупорядочена, поэтому считаем C(52,5) = 52! / (5! × 47!)
   2. Перемножим пять убывающих множителей: 52 × 51 × 50 × 49 × 48 = 311 875 200
   3. Разделим на 5! = 120: 311 875 200 / 120 = 2 598 960
   4. Вторая строка — это промежуточный шаг первой; именно это и значит, что рука есть упорядоченная раздача, делённая на число упорядочиваний

   2 598 960 — то число, на которое делится каждая покерная вероятность, и самая востребованная клетка на этой странице. Здесь две строки стоит читать вместе, потому что строка перестановок буквально и есть числитель до деления на 5!: руку из пяти карт можно раздать 311 875 200 упорядоченными способами, и на каждую руку приходится 120 из них. Увидеть, что неупорядоченное число есть упорядоченное, делённое на число упорядочиваний, — самый быстрый способ перестать путать эти два.

4. Шесть предметов, взять все шесть: одно сочетание, 720 перестановок

   1. Взять всё можно только одним способом, поэтому C(6,6) = 1
   2. Перестановки — это упорядочивания всех шести предметов: P(6,6) = 6! = 720
   3. Множитель между строками равен 720 = 6!, то есть правило r! при r = n

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

5. Три вкуса, пять шариков: r больше n

   1. Пять шариков из трёх вкусов, порядок не учитывается, повторы разрешены: C = C(3 + 5 − 1, 5) = C(7,5) = 21
   2. С учётом порядка тоже P = 3⁵ = 243
   3. И то и другое законно только потому, что повторения включены: с выключенными выбрать пять из трёх невозможно, и страница отклоняет такой ввод

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

Оба числа остаются точными целыми лишь до некоторой границы, а за ней страница отказывается считать вместо того, чтобы округлять. Числа растут быстро — сто предметов, выбранных по пятьдесят, дают тридцать цифр, — а числа с плавающей точкой перестают вмещать каждое целое точно где-то около шестнадцатой цифры, поэтому такое большое число вернулось бы с неверными последними цифрами и выглядело бы при этом совершенно обычным. Вместо того чтобы печатать число, неверное так, что этого никто не заметит, страница выбрасывает ошибку для чисел за пределами точного диапазона; тот же отказ касается пула больше тысячи предметов и любого отрицательного числа. Ещё два ограничения: страница только считает и ничего больше — она не перечисляет сочетания, не выводит их списком и не вычисляет вероятность вытащить одно из них, которая равна числу, делённому на общее количество. И переключатель повторений означает ровно одно: один и тот же предмет можно взять больше одного раза; он не моделирует выбор без возвращения против выбора с возвращением в том смысле, какой вкладывает колода карт, где пул уменьшается по мере выбывания карт.

В чём разница между сочетанием и перестановкой?

Сочетание не учитывает порядок выбора, а перестановка его считает. Выбрать трёх человек в комитет из десяти — это сочетания, потому что комитет ABC — тот же комитет, что и CBA; вручить тем же трём первое, второе и третье место — перестановки, потому что назначения разные. Эти два числа никогда не близки: число перестановок равно числу сочетаний, умноженному на r! — число способов упорядочить выбранные r предметов. Обе строки печатаются на этой странице именно для того, чтобы множитель никогда не приходилось угадывать: при r = 3 он равен 6, а при r = 5 — 120.

Что означает nCr на моём калькуляторе?

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

Что меняется, когда я разрешаю повторения?

Меняются обе формулы и заодно то, какие входные данные законны. С выключенными повторениями число перестановок — убывающее произведение n × (n − 1) × …, а число сочетаний делит его на r!; с включёнными число перестановок это просто n в степени r, а число сочетаний становится числом мультимножеств, которое для n предметов, взятых по r, равно C(n + r − 1, r). Именно законность и застаёт врасплох: с выключенными повторениями r больше n невозможно вовсе и отклоняется, а с включёнными это обычный запрос — как пять шариков из трёх вкусов.

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

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

Переключатель повторений означает выбор с возвращением?

Не в том смысле, какой вкладывает в это выражение колода карт. Переключатель говорит лишь, что один и тот же предмет можно выбрать больше одного раза, — а это и есть то, что даёт выбор с возвращением в пуле независимых вариантов. В карточной задаче пул к тому же уменьшается по мере выбывания карт, и формулы выше уже учитывают это убывающим произведением в варианте без повторений: рука из пяти карт — это C(52,5), а не 52 в пятой степени. Так что переключатель отвечает на вопрос, разрешён ли повтор, а уменьшение пула обеспечивает формула, а не переключатель.

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

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

• 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
• 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
• Multichoose — from Wolfram MathWorld (the number of multisets of a given length on a given number of symbols, which is the combinations with repetition count this page switches to) — Wolfram MathWorld