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

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

Популярный AI Skill PRO

Введите расчет

Математическая формула

CR(n,r)=(n+r−1)!r!(n−1)!C^{R}(n,r) = \frac{(\text{n} + \text{r} - 1)!}{\text{r}!\,(\text{n} - 1)!}
Статистика использования

Реклама

Результаты

Число сочетаний с повторениями
70
Общее число типов элементов (n) 5
Сколько элементов выбираем (r) 4

Сообщить об ошибке на этой странице

Что считает этот калькулятор

Калькулятор сочетаний с повторениями показывает, сколькими способами можно выбрать r элементов из n различных типов, если повторения разрешены, а порядок выбора не важен. Это базовая задача комбинаторики и теории вероятностей, которую часто называют методом «звёзд и палочек» (stars and bars). Поскольку каждый тип можно брать несколько раз, итоговое число получается больше, чем при обычных сочетаниях без повторений.

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

Какие данные нужно ввести

  • Общее число типов элементов (n): сколько различных категорий доступно для выбора — например, 3 сорта мороженого.
  • Сколько элементов выбираем (r): сколько всего раз вы делаете выбор, причём один и тот же тип может повторяться.

Введите оба значения целыми числами — и калькулятор сразу выдаст один результат: количество различных мультимножеств (неупорядоченных наборов с допустимыми повторами).

Формула

В основе расчёта лежит стандартная формула сочетаний с повторениями:

$$C^{R}(n,r) = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$

Внутри калькулятор вычисляет три факториала — \((n + r - 1)!\), \(r!\) и \((n - 1)!\) — и выполняет деление по формуле. Расчёт ведётся точно, в целых числах, поэтому результат — это точное целое число, а не приближённая оценка.

Реклама
Расположение звёзд и перегородок, представляющее сочетания с повторениями
Метод звёзд и перегородок объясняет, почему количество равно \(C(n+r-1, r)\).

Разбор примера

Допустим, в кафе-мороженом есть n = 3 сорта, и вы хотите стаканчик с r = 2 шариками, причём сорт можно повторять. Подставляем \(n = 3\) и \(r = 2\):

  • \(n + r - 1 = 3 + 2 - 1 = 4\)
  • $$C(4, 2) = \frac{4!}{2! \cdot 2!} = \frac{24}{2 \cdot 2} = 6$$

Значит, существует 6 вариантов стаканчика с двумя шариками: AA, BB, CC, AB, AC и BC. Калькулятор мгновенно выдаёт 6.

Частые вопросы

Чем это отличается от обычных сочетаний? Обычные сочетания \(C(n, r)\) запрещают повторы — каждый элемент берётся не более одного раза. Сочетания с повторениями допускают многократный выбор одного и того же типа, поэтому используется формула \(C(n + r - 1, r)\).

Важен ли здесь порядок? Нет. Наборы AB и BA считаются одинаковыми. Если бы порядок имел значение, нужно было бы применять размещения (перестановки).

Может ли r быть больше n? Да. Так как повторения разрешены, можно выбрать больше элементов, чем есть типов — например, взять 5 шариков из 3 сортов вполне допустимо, и число вариантов при этом будет больше.

Дополнительные рабочие примеры

Каждый пример ниже использует одно и то же тождество, \(C^{R}(n,r) = \binom{n+r-1}{r} = \frac{(n+r-1)!}{r!\,(n-1)!}\), где \(n\) — количество доступных типов различных предметов, а \(r\) — количество выбираемых предметов. Порядок не имеет значения, и каждый тип может быть использован повторно, поэтому каждый исход — это мультимножество.

Пример 1 — Три одинаковых кубика (n = 6, r = 3)

Вы бросаете три неразличимых шестигранных кубика и записываете только набор выпавших граней (так что 1-3-6 и 6-3-1 считаются одним исходом). Есть \(n = 6\) типов граней и \(r = 3\) броска, с повторением, разрешённым, потому что два кубика могут показать одинаковую грань.

Верхний индекс: \(n + r - 1 = 6 + 3 - 1 = 8\).

$$C^{R}(6,3) = \binom{8}{3} = \frac{8!}{3!\,5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56$$

Итак, есть 56 отличных неупорядоченных комбинаций граней. Обратите внимание, что это намного меньше, чем \(6^3 = 216\) упорядоченных бросков — 216 упорядоченных исходов сворачиваются в 56 мультимножеств, но неравномерно (тройка как 4-4-4 имеет одно упорядочение, в то время как 1-3-6 имеет шесть), что именно почему вероятности сумм кубиков должны вычисляться из 216 упорядоченных бросков, а не из 56 мультимножеств.

Пример 2 — Больше порций, чем вкусов (n = 3, r = 5)

Кафе мороженого предлагает 3 вкуса, и вы заказываете контейнер на 5 порций; несколько порций одного вкуса разрешены, и порядок упаковки не имеет значения. Здесь \(r = 5\) больше, чем \(n = 3\), что невозможно для комбинаций без повторения, но здесь это совершенно нормально.

Верхний индекс: \(n + r - 1 = 3 + 5 - 1 = 7\).

$$C^{R}(3,5) = \binom{7}{5} = \frac{7!}{5!\,2!} = \frac{7 \times 6}{2 \times 1} = \frac{42}{2} = 21$$

Есть 21 возможный контейнер. Сокращение \(5!\) вместо \(2!\) — ярлык здесь: потому что \(\binom{7}{5} = \binom{7}{2}\), только два множителя числителя остаются. В терминах звёзд и палочек вы размещаете 5 звёзд (порций) и \(n - 1 = 2\) палочки (разделители вкусов) в 7 позиций — например \(\star\star\,|\,\star\,|\,\star\star\) означает 2 ванили, 1 шоколад, 2 клубники.

Пример 3 — Два граничных случая (r = 1 и n = 1)

Выбор одного предмета (n = 4, r = 1). Вы выбираете один размер напитка из 4. С только одним выбором повторение никогда не может произойти, поэтому ответ должен быть просто количеством типов:

$$C^{R}(4,1) = \binom{4+1-1}{1} = \binom{4}{1} = \frac{4!}{1!\,3!} = \frac{4}{1} = 4$$

что дает 4 исхода — столбец \(r = 1\) любой такой таблицы всегда просто \(n\).

Только один тип (n = 1, r = 7). Торговый автомат запасает один продукт, и вы покупаете 7 единиц:

$$C^{R}(1,7) = \binom{1+7-1}{7} = \binom{7}{7} = \frac{7!}{7!\,0!} = \frac{5040}{5040 \times 1} = 1$$

Есть ровно одно мультимножество — "семь единственного доступного предмета" — потому что с одним типом выбора больше не остаётся. Формально требуется \(n - 1 = 0\) палочек, все 7 позиций должны быть звёздами, и \(\binom{7}{7} = 1\). Та же логика делает \(C^{R}(n,0) = 1\) для любого \(n\): выбор ничего — это одна допустимая (пустая) выборка, что почему \(0! = 1\) — соглашение, которое держит формулу согласованной.

Реклама

Таблица справки комбинаций с повторением

Точные значения \(C^{R}(n,r) = \binom{n+r-1}{r}\) для 1–8 типов предметов, выбираемых 1–6 раз. Читайте вниз к вашему количеству типов \(n\), затем поперёк к количеству выборов \(r\).

Количество неупорядоченных выборок с разрешённым повторением
n (типы) r = 1 r = 2 r = 3 r = 4 r = 5 r = 6
1 1 1 1 1 1 1
2 2 3 4 5 6 7
3 3 6 10 15 21 28
4 4 10 20 35 56 84
5 5 15 35 70 126 210
6 6 21 56 126 252 462
7 7 28 84 210 462 924
8 8 36 120 330 792 1716

Как читать паттерны

  • Каждая строка — диагональ треугольника Паскаля. Строка \(n = 1\) — постоянная последовательность 1, строка \(n = 2\) — натуральные числа \(2, 3, 4, \dots\), строка \(n = 3\) — треугольные числа \(3, 6, 10, 15, 21, 28\), и строка \(n = 4\) — тетраэдральные числа \(4, 10, 20, 35, 56, 84\). Это просто \(\binom{n+r-1}{r}\) вдоль фиксированного \(n\).
  • Таблица симметрична при сдвиге. Потому что \(\binom{n+r-1}{r} = \binom{n+r-1}{n-1}\), мы получаем \(C^{R}(n,r) = C^{R}(r+1,\,n-1)\). Например, \(C^{R}(6,3) = 56 = C^{R}(4,5)\), и \(C^{R}(8,3) = 120 = C^{R}(4,7)\). Обмен ролями "типы" и "выборы" таким образом часто превращает длинное умножение в короткое.
  • Рост полиномиален по r, степени n − 1. Держа \(n\) фиксированным, \(C^{R}(n,r) = \frac{(r+1)(r+2)\cdots(r+n-1)}{(n-1)!}\), полином степени \(n-1\) — линейный для \(n = 2\), квадратичный для \(n = 3\), кубический для \(n = 4\). Держа \(r\) фиксированным и растя \(n\), ведёт себя так же с поменянными ролями (степень \(r\) в \(n\)). В любом случае количества остаются далеко ниже \(n^{r}\) количества упорядоченных выборок с повторением.
  • Каждый элемент — сумма одного выше и одного слева (где оба существуют): \(C^{R}(n,r) = C^{R}(n-1,r) + C^{R}(n,r-1)\). Проверьте \(126 = 70 + 56\) в клетке \(n = 6\), \(r = 4\). Это рекуррентное соотношение — быстрый способ расширить таблицу вручную.

Как вычислить это вручную

Картина звёзд и палочек

Перед арифметикой, это помогает видеть почему формула имеет такую форму. Представьте выборку как \(r\) идентичных звёзд (предметы, которые вы берёте) разделённых на \(n\) групп \(n-1\) палочками (разделители между типами последовательных предметов). Количество звёзд в группе \(i\) — это сколько копий типа \(i\) вы выбрали. Каждое расположение \(r\) звёзд и \(n-1\) палочек соответствует ровно одной допустимой выборке, и есть \(r + (n-1) = n + r - 1\) позиций в ряду. Подсчёт выборок, таким образом, означает выбор, какие \(r\) из этих \(n+r-1\) позиций содержат звёзды:

$$C^{R}(n,r) = \binom{n+r-1}{r} = \binom{n+r-1}{n-1}$$

Например, с \(n = 4\) типами и \(r = 5\) выборами, ряд \(\star\,|\,|\,\star\star\star\,|\,\star\) имеет 8 позиций и означает 1 тип A, ни одного типа B, 3 типа C, 1 тип D.

Пошаговая процедура

  1. Проверьте входные данные. Подтвердите, что \(n\) и \(r\) — целые числа с \(n \ge 1\) и \(r \ge 0\). В отличие от комбинаций без повторения, \(r\) может превышать \(n\) — повторение разрешено, поэтому нет верхней границы для \(r\).
  2. Вычислите верхний индекс. Вычислите \(N = n + r - 1\). Это общее количество позиций звёзд и палочек.
  3. Напишите бином. \(C^{R}(n,r) = \dbinom{N}{r} = \dfrac{N!}{r!\,(n-1)!}\). Никогда не разворачивайте эти факториалы полностью — \(N!\) взрывается быстро и все большие числа сокращаются.
  4. Сократите \((n-1)!\) против \(N!\). Поскольку \(N - r = n - 1\), частное \(N!/(n-1)!\) оставляет ровно \(r\) нисходящих множителей в числителе:
$$C^{R}(n,r) = \frac{(n+r-1)(n+r-2)\cdots(n)}{r!}$$
  1. Умножьте \(r\) членов в числителе, затем разделите на \(r!\). Если \(r\) больше чем \(n-1\), используйте симметрию \(\binom{N}{r} = \binom{N}{n-1}\) сначала так чтобы вы умножили меньшее количество множителей вместо этого.
  2. Здравая проверка, что результат — целое число. Биномиальный коэффициент всегда целое число, поэтому любая остаточная дробь или остаток означает арифметическую ошибку. Две дополнительных быстрых проверки: \(r = 1\) должно дать ровно \(n\), и \(n = 1\) должно дать ровно 1.

Проработанный пример (n = 5, r = 4)

Четыре порции замороженного йогурта из 5 добавок, повторения разрешены, порядок не имеет значения.

  • Шаг 2: \(N = 5 + 4 - 1 = 8\).
  • Шаг 3: \(C^{R}(5,4) = \dfrac{8!}{4!\,4!}\).
  • Шаг 4: сократите \((n-1)! = 4!\), оставляя \(r = 4\) нисходящих множителей от 8 вниз к \(n = 5\): \(\dfrac{8 \times 7 \times 6 \times 5}{4!}\).
  • Шаг 5: \(\dfrac{1680}{24} = 70\).
  • Шаг 6: 70 — целое число, и оно совпадает с клеткой \(n = 5\), \(r = 4\) справочной таблицы выше.

Ответ: 70 отличных комбинаций добавок. Полезный контраст: те же входные данные дают \(5^4 = 625\), если порядок имеет значение, и только \(\binom{5}{4} = 5\), если повторение запрещено — так всегда решите, применяются ли порядок и повторение, перед выбором формулы.

Последнее обновление:

Самые популярные в разделе Математика и статистика

Все калькуляторы раздела Математика и статистика