Что такое сочетание с повторениями?
Сочетание с повторениями (его также называют сочетанием из мультимножества) показывает, сколькими способами можно выбрать r элементов из n различных типов, если повторы разрешены, а порядок выбора не имеет значения. В отличие от обычных сочетаний, один и тот же элемент можно выбрать несколько раз. Этот калькулятор вычисляет такое количество по формуле для мультимножеств \(C(n+r-1, r)\).
Как пользоваться калькулятором
Введите число различных типов элементов n (например, 5 сортов мороженого) и количество элементов, которые вы хотите выбрать — r (например, 3 шарика). Калькулятор выдаст число различных мультимножеств — то есть наборов, которые отличаются лишь тем, какие типы в них входят и сколько раз, без учёта порядка.
Разбор формулы
Результат определяется выражением
$$\overline{C}(n,r) = \binom{n+r-1}{r} = \frac{\left(\text{Item types} + \text{Choose} - 1\right)!}{\text{Choose}!\,\left(\text{Item types} - 1\right)!}$$Понять её помогает модель «звёзд и перегородок»: разместите \(r\) одинаковых звёздочек в \(n\) ячейках, разделённых \(n-1\) перегородками; каждое такое расположение соответствует одному набору. Чтобы избежать переполнения при работе с факториалами, калькулятор вычисляет биномиальный коэффициент через последовательное умножение.
Разбор примера
Предположим, в кафе-мороженом предлагают \(n = 5\) сортов, а вы хотите вазочку из \(r = 3\) шариков с разрешёнными повторами. Тогда
$$C(5+3-1, 3) = C(7, 3) = \frac{7!}{3!\cdot 4!} = 35$$Значит, можно собрать 35 различных вазочек.
Частые вопросы
Чем это отличается от обычного сочетания? В обычном сочетании \(C(n, r)\) повторы запрещены, а здесь один и тот же тип можно выбирать несколько раз.
Может ли r быть больше n? Да. Поскольку повторы разрешены, \(r\) может превышать \(n\) — например, выбрать 10 шариков из 3 сортов вполне допустимо.
А если r равно 0? Не выбрать ничего можно ровно одним способом (пустое мультимножество), поэтому результат равен 1.
