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

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

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

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

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

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

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

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