Сочетания с повторениями
Главный вопрос
Сколькими способами можно выбрать $k$ предметов из $n$ типов, если разрешено выбирать один и тот же тип несколько раз и порядок не имеет значения?
Формальное определение
Сочетание с повторениями (также называемое мультимножественным коэффициентом) подсчитывает количество способов выбрать $k$ элементов из множества $n$ типов, где:
- Повторения РАЗРЕШЕНЫ — можно выбирать один и тот же предмет несколько раз
- Порядок НЕ имеет значения — выбор {A, A, B} — это то же самое, что {A, B, A}
Формула:
$$\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1} = \frac{(n + k - 1)!}{k!\,(n - 1)!}$$
где $n$ = количество доступных типов, $k$ = количество выбираемых предметов.
Сравнительная таблица
| Порядок важен | Порядок не важен | |
|---|---|---|
| Без повторений | Размещение $P(n,k) = \frac{n!}{(n-k)!}$ | Сочетание $\binom{n}{k}$ |
| С повторениями | $n^k$ | $\binom{n+k-1}{k}$ ← Мы здесь! |