Что такое сочетание с повторениями?
Сочетание с повторениями (его ещё называют «мультивыбор») показывает, сколькими способами можно выбрать r элементов из n различных типов, если порядок выбора не важен, а один и тот же тип разрешается брать несколько раз. Каждый результат — это мультимножество. Например, если взять 2 шарика мороженого из 3 вкусов с возможностью повторов, получатся такие наборы, как {ваниль, ваниль} или {ваниль, шоколад}.
Как пользоваться калькулятором
Введите \(n\) — количество различных объектов или типов, из которых выбираете, и \(r\) — размер выборки, которую хотите составить. Оба значения должны быть целыми неотрицательными числами. Нажмите «Рассчитать», и калькулятор вернёт \(C^R(n,r)\) — число различных мультимножеств размера \(r\).
Разбираем формулу
Результат равен биномиальному коэффициенту \(C(n + r - 1, r)\), который раскрывается как $$C^R(n, r) = \binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$ Это классический результат метода «звёзд и палочек»: мы раскладываем \(r\) одинаковых звёздочек по \(n\) ячейкам, разделённым \(n - 1\) палочками. Чтобы избежать переполнения при работе с факториалами, калькулятор последовательно умножает накопленное произведение на \((n - 1 + i)\) и делит на \(i\) для \(i\) от 1 до \(r\):
$$C^R(n,r) = \prod_{i=1}^{r} \frac{n - 1 + i}{i}$$
Разбор примера
Пусть \(n = 10\) и \(r = 3\):
$$C^R(10,3) = C(12,3) = \frac{12 \times 11 \times 10}{3 \times 2 \times 1} = \frac{1320}{6} = 220$$Значит, существует 220 способов выбрать 3 элемента из 10 типов с разрешёнными повторами.
Частые вопросы
Чем это отличается от обычного сочетания? Обычное сочетание \(C(n,r)\) запрещает повторы, а сочетание с повторениями допускает, что один и тот же элемент берётся несколько раз, поэтому итоговое число, как правило, больше.
Что будет при r = 0? Способ ничего не выбирать ровно один, поэтому \(C^R(n,0) = 1\) для любого \(n \geq 1\).
Что будет при n = 0? Если элементов нет, а \(r > 0\), результат равен 0; пустой случай \(n = 0, r = 0\) по соглашению равен 1.
