Зірки та риски

Зірки та риски (англ. stars and bars) — наочна допомога для виведення певних комбінаторних теорем. Її популяризував Вільям Феллер у своїй класичній книзі про ймовірність. Цю техніку можна використовувати для багатьох простих проблем підрахунку, таких як скільки існує способів, щоб розмістити $n$ невідрізненних кульок у $k$ відрізненних кошиків.

Формулювання теорем

Перша теорема

Для будь-якої пари додатних цілих $n$ і $k$, кількість відмінних $k-$кортежів додатних цілих чисел, чия сума є $n$, задається біноміальним коефіцієнтом $\textstyle {n-1 \choose k-1}.$

Друга теорема

Для будь-якої пари додатних цілих $n$ і $k$, кількість відмінних $k-$кортежів невід'ємних цілих чисел, чия сума становить $n$, задається біноміальним коефіцієнтом ${\tbinom {n+k-1}{n}}$ або, тотожно, через числом мультимножин $\left(\!{\tbinom {k}{n}}\!\right),$ яке лічить мультимножини потужності $n,$ елементи яких узяті із множини з $k$ елементів (для $n=k=0$ обидва ці числа визначені в 1).

Доведення

Перша теорема

Припустимо хтось має n предметів (які ми представлятимемо зірками; у прикладі нижче n = 7) які необхідно помістити в k кошиків (у прикладі k = 3), так що кожен кошик містить щонайменше один предмет; гравець розрізняє кошики (скажімо, вони пронумеровані від 1 до k), але не розрізняє n зірок (отже розташовання відрізняються кількістю зірок присутніх у кожному кошику; насправді розташовання кожне представлене k-кортежем додатних цілих як у твердженні теореми). Замість розміщення зірок у кошиках треба треба розміщати їх на лінії:

★ ★ ★ ★ ★ ★ ★ Мал. 1: сім предметів представлено зірками

де зірки для першого кошика братимуться зліва, за ними йтимуть зірки для другого кошика і т.д. Отже, розташовання буде визначено коли гравець знатиме номер першої зірки яка йде у другий кошик, номер першої зірки яка йде у третій кошик і т.д. Гравець може позначити це розміщенням $k-1$ розділових рисок десь поміж зірок; оскільки жоден з кошиків не може бути порожнім, дозволено розміщати лише одна риску між певною парою зірок:

★ ★ ★ ★ | ★ | ★ ★

Мал. 2: дві риски окреслюють три кошики, що містять 4, 1 і 2 предмети

Отже, гравець може розглядати n зірок як зафіксовані предмети що визначають $n-1$ розривів, в кожному з яких може бути чи не бути одна риска. Гравець має обрати $k-1$ таких розривів у яких будуть риски; звідси, існує ${\tbinom {n-1}{k-1}}$ можливих розташувань (див. комбінацій).

Друга теорема

Якщо $n>0$, гравець може застосувати першу теорему до $n+k$ предметів, що дає ${\tbinom {n+k-1}{k-1}}={\tbinom {n+k-1}{n}}$ розташувань зі щонайменше одним предметом у кожному кошику, і тоді видалити по одному предмету з кожного кошику для отримання розподілу з $n$ предметів у $k$ кошиків, при тому, що деякі кошики можуть бути порожніми. Наприклад, розміщення 10 предметів у 5 кошиках, за умови, що кошики можуть бути порожніми, тотожно розміщенню 15 предметів у 5 кошиках із вимогою мати не менше одного предмету у кожному кошику. Інший спосіб отримати цей біноміальний коефіцієнт: розглянути послідовність із $n+k-1$ символів, серед яких гравець має визначити $n$ зірок і $k-1$ рисок (які в цьому випадку можуть іти одна за одною).

У випадку $k=0$ (взагалі без кошиків) дозволяє 0 розташувань, хіба що $n$ також дорівнює $0$ (немає предметів), тоді існує одне розташовання.

Див. також

• Дванадцятикратний шлях