Звезды и столбцы

Звезды и столбцы

Введение

Stars and Bars — это классический комбинаторный метод, позволяющий считать количество способов распределения одинаковых объектов по различным контейнерам.

Идея очень простая:

• звёздочки * обозначают объекты,
• столбцы | разделяют контейнеры.

Теорема

Постановка задачи

Дано:

• $k$ одинаковых объектов,
• $n$ различных контейнеров.

Сколькими способами можно распределить эти $k$ объектов по $n$ контейнерам?

Мы можем представить распределение как последовательность из:

• $k$ звёздочек *,
• $n-1$ столбцов .