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

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

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

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

Для будь-якої пари додатних цілих і , кількість відмінних кортежів додатних цілих чисел, чия сума є , задається біноміальним коефіцієнтом

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

Для будь-якої пари додатних цілих і , кількість відмінних кортежів невід'ємних цілих чисел, чия сума становить , задається біноміальним коефіцієнтом або, тотожно, через числом мультимножин яке лічить мультимножини потужності елементи яких узяті із множини з елементів (для обидва ці числа визначені в 1).

Доведення

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

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

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

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

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

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

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

Якщо , гравець може застосувати першу теорему до предметів, що дає розташувань зі щонайменше одним предметом у кожному кошику, і тоді видалити по одному предмету з кожного кошику для отримання розподілу з предметів у кошиків, при тому, що деякі кошики можуть бути порожніми. Наприклад, розміщення 10 предметів у 5 кошиках, за умови, що кошики можуть бути порожніми, тотожно розміщенню 15 предметів у 5 кошиках із вимогою мати не менше одного предмету у кожному кошику. Інший спосіб отримати цей біноміальний коефіцієнт: розглянути послідовність із символів, серед яких гравець має визначити зірок і рисок (які в цьому випадку можуть іти одна за одною).

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

Примітки

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

Див. також

  • Дванадцятикратний шлях
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.