Что такое сочетания с повторениями?
Сочетания с повторениями показывают, сколькими способами можно выбрать r элементов из n различных типов, если один и тот же тип разрешено брать несколько раз, а порядок выбора не имеет значения. Эту величину обычно обозначают как nHr и называют мультимножественным коэффициентом. Она отвечает на вопросы вроде: «Сколько разных порций можно собрать из 4 вкусов мороженого, если взять 2 шарика и повторы допускаются?»
Как пользоваться калькулятором
Введите количество различных типов n (не меньше 1) и количество выбираемых элементов r (ноль или больше). Нажмите «Рассчитать», и инструмент вернёт nHr — точное число различных мультимножеств. Оба значения — это обычные неотрицательные целые числа; единицы измерения переводить не нужно.
Разбор формулы
Базовое тождество выглядит так: $$\overline{C}(n,r) = \binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$ Идея проста: если выстроить в ряд r выбранных элементов и (n − 1) разделителей между типами, получится n + r − 1 позиций, и нам остаётся выбрать, где разместить элементы (или разделители). Чтобы не считать огромные факториалы, калькулятор вычисляет биномиальный коэффициент через устойчивый мультипликативный цикл: умножая на \((m - k + i)\) и деля на \(i\) для \(i = 1..k\), где \(m = n + r - 1\), а \(k = \min(r, n - 1)\).
Разбор примера
При значениях по умолчанию n = 4, r = 2: $$nHr = C(4 + 2 - 1, 2) = C(5, 2) = \frac{5 \cdot 4}{2 \cdot 1} = 10$$ Вот эти десять сочетаний из типов {a, b, c, d}: aa, ab, ac, ad, bb, bc, bd, cc, cd, dd.
Частые вопросы
Чем это отличается от обычных сочетаний? В обычных сочетаниях \(C(n, r)\) повторы запрещены, поэтому каждый элемент берётся не более одного раза; здесь же повторы разрешены, и итоговое число получается больше.
Что если r = 0? Существует ровно одно сочетание — пустой выбор, поэтому nHr = 1.
Что если n = 1? Когда тип всего один, его придётся выбрать r раз, поэтому мультимножество ровно одно и nHr = 1 при любом r.
