Зірки і смуги

Зірки і смуги — це математичний прийом для розв'язання певних комбінаторних задач. Він виникає щоразу, коли ми хочемо підрахувати кількість способів згрупувати однакові об'єкти.

Коли підходить цей алгоритм?

• Чи розподіляємо $n$ однакових (нерозрізнюваних) об'єктів по $k$ різних скриньках?
• Чи задача зводиться до кількості розв'язків рівняння $x_1 + x_2 + \dots + x_k = n$ у цілих числах із нижніми межами ($x_i \ge 0$ або $x_i \ge a_i$)?
• Чи потрібні ще й верхні межі на $x_i$? (якщо так → Принцип включення-виключення; а якщо об'єкти різні — це просто біноміальний коефіцієнт)

Теорема

Кількість способів розкласти $n$ однакових об'єктів у $k$ позначених скриньок дорівнює

$$\binom{n + k - 1}{n}.$$

Доведення полягає в тому, щоб перетворити об'єкти на зірки і відокремити скриньки за допомогою смуг (звідси й назва). Наприклад, записом $\bigstar | \bigstar \bigstar |~| \bigstar \bigstar$ можна зобразити таку ситуацію: у першій скриньці один об'єкт, у другій скриньці два об'єкти, третя порожня, а в останній скриньці два об'єкти. Це один зі способів розподілити 5 об'єктів у 4 скриньки.

Має бути цілком очевидно, що кожний розподіл можна зобразити за допомогою $n$ зірок і $k - 1$ смуг, і що кожна перестановка зірок і смуг із $n$ зірок та $k - 1$ смуг відповідає одному розподілу. Отже, кількість способів розподілити $n$ однакових об'єктів у $k$ позначених скриньок дорівнює кількості перестановок $n$ зірок і $k - 1$ смуг. Біноміальний коефіцієнт дає нам бажану формулу.

Кількість сум невід'ємних цілих чисел

Ця задача є прямим застосуванням теореми.

Ми хочемо підрахувати кількість розв'язків рівняння

$$x_1 + x_2 + \dots + x_k = n$$

за умови $x_i \ge 0$.

Знову ж таки, розв'язок можна зобразити за допомогою зірок і смуг. Наприклад, розв'язок $1 + 3 + 0 = 4$ для $n = 4$, $k = 3$ можна зобразити як $\bigstar | \bigstar \bigstar \bigstar |$.

Легко бачити, що це саме теорема про зірки і смуги. Отже, розв'язком є $\binom{n + k - 1}{n}$.

Кількість сум додатних цілих чисел

Друга теорема дає гарну інтерпретацію для додатних чисел. Розглянемо розв'язки рівняння

$$x_1 + x_2 + \dots + x_k = n$$

за умови $x_i \ge 1$.

Ми можемо розглянути $n$ зірок, але цього разу між зірками можна поставити щонайбільше одну смугу, оскільки дві смуги між зірками означали б $x_i=0$, тобто порожню скриньку. Між зірками є $n-1$ проміжок для розміщення $k-1$ смуг, тому розв'язком є $\binom{n-1}{k-1}$.

Кількість сум цілих чисел з нижніми межами

Це легко узагальнити на суми цілих чисел з різними нижніми межами. Тобто ми хочемо підрахувати кількість розв'язків рівняння

$$x_1 + x_2 + \dots + x_k = n$$

за умови $x_i \ge a_i$.

Після заміни $x_i' := x_i - a_i$ ми отримуємо видозмінене рівняння

$$(x_1' + a_i) + (x_2' + a_i) + \dots + (x_k' + a_k) = n$$ $$\Leftrightarrow ~ ~ x_1' + x_2' + \dots + x_k' = n - a_1 - a_2 - \dots - a_k$$

за умови $x_i' \ge 0$. Отже, ми звели задачу до простішого випадку з $x_i' \ge 0$ і знову можемо застосувати теорему про зірки і смуги.

Кількість сум цілих чисел з верхніми межами

За допомогою принципу включень-виключень можна також обмежити цілі числа верхніми межами. Дивіться розділ Number of upper-bound integer sums у відповідній статті.

Задачі для практики

• Codeforces - Array
• Codeforces - Kyoya and Coloured Balls
• Codeforces - Colorful Bricks
• Codeforces - Two Arrays
• Codeforces - One-Dimensional Puzzle

Відеоматеріали