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