Звёзды и полосы

Введение

Звёзды и перегородки — это стандартный комбинаторный метод, используемый для подсчёта числа способов распределить одинаковые объекты по различимым контейнерам.

Он особенно полезен в задачах про целочисленные решения, группировку и распределения.

Теорема

Формулировка задачи

Предположим, у нас есть $k$ одинаковых объектов, и мы хотим распределить их по $n$ различимым ящикам.

Удобный способ визуализировать это — представить:

• каждый объект звездой *
• каждый разделитель между ящиками перегородкой |

Тогда мы располагаем:

• $k$ звёзд
• $n - 1$ перегородок

Например, если мы помещаем $4$ одинаковых объекта в ящика, некоторые возможные расположения: