Сочетания с повторениями

Идея и определение

Сочетание с повторениями — набор заданного размера, в котором важны количества предметов каждого вида, но не порядок выбора. Два яблока и одна груша — тот же набор, что груша и два яблока. Предполагается, что каждый вид можно брать сколько угодно раз в пределах размера набора. Если в магазине осталась одна груша, стандартная формула уже не описывает задачу.

Для $n$ видов и $k$ предметов обозначим количества через $x_1,\ldots,x_n$. Нужно посчитать решения $x_1+\cdots+x_n=k$ в неотрицательных целых числах. Кодируем предметы $k$ звёздочками, а границы видов — $n-1$ перегородками. Соседние перегородки означают нулевое количество соответствующего вида. Всего $n+k-1$ позиций, из них выбираем $k$ под звёздочки.

Границы модели

Формула $\binom{n+k-1}{k}$ требует $n\ge1$. При $k=0$ есть один пустой набор. Если каждого вида нужно хотя бы по одному, сначала выдаём по одному предмету, а затем распределяем оставшиеся $k-n$; решение возможно лишь при $k\ge n$. Это дополнительный комбинаторный материал, а не обязательная тема всех школьных классов.

Три примера

1. Покупаем 4 пирожных трёх видов с неограниченным запасом. Наборы задаются тройками количеств; их $\binom{6}{4}=15$, а не $3^4$: последовательности покупок здесь не различаются.
2. Распределяем 5 одинаковых жетонов между тремя подписанными коробками, пустые разрешены. Получаем $\binom{7}{2}=21$ распределение. Коробки различимы, жетоны — нет.
3. В каждую из трёх коробок кладём хотя бы один из 7 одинаковых жетонов. После обязательных трёх остаются четыре: $\binom{6}{2}=15$ вариантов.

Типичные ошибки

Нельзя применять эту формулу к различимым жетонам: там нужно учитывать, какой именно жетон попал в коробку. Нельзя также считать все найденные наборы равновероятными без отдельной модели случайного выбора: подсчёт числа наборов сам по себе не задаёт вероятности.