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

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

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

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

Для будь-якої пари додатних цілих ${\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-кортежем додатних цілих як у твердженні теореми). Замість розміщення зірок у кошиках треба треба розміщати їх на лінії:

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

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

★ ★ ★ ★ | ★ | ★ ★

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

Отже, гравець може розглядати 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}$ (немає предметів), тоді існує одне розташовання.

Примітки

1. Feller, W. (1950) An Introduction to Probability Theory and Its Applications, Wiley, Vol 1, 2nd ed.

Див. також

• ^[en]