Звијезде и линије (комбинаторика)

У контексту комбинаторне математике, звијезде и линије представљају графичку помоћ за извођење одређених комбинаторних теорема. Вилиам Фелер га је популаризовао у својој класичној књизи о вјероватноћи. Може да се користити за рјешавање многих једноставних проблема бројања, као на примјер на колико начина може да се расподјели n идентичних лоптица у k различитих посуда.

Дефиниције теоремe

Метода звијезда и линија се често уводи посебно да би се доказале следеће две теореме елементарне комбинаторике.

Прва теорема

За сваки пар позитивних цијелих бројева n и k, број k-торки позитивних цијелих бројева чија је сума n једнак је броју (k − 1) елемената подскупа скупа са n − 1 елементом.

Оба ова броја су представљена биномним коефицијентом $\textstyle {n-1 \choose k-1}$. На пример, када је n = 3 и k = 2, торке које се броје по теореми су (2, 1) и (1, 2), и има их ${\tbinom {3-1}{2-1}}=2$.

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

За сваки пар позитивних цијелих бројева n и k, број k-торки ненегативних цијелих бројева чија је сума n једнак је броју мултисетова кардиналности k − 1 узетих из сета велилине n + 1.

Оба броја се добијају из мултисета од $\left(\!{\tbinom {n+1}{k-1}}\!\right)$, или еквивалентно биномским коефицијентом ${\tbinom {n+k-1}{k-1}}={\tbinom {n+k-1}{n}}$ или мултисет бројем ${\big (}\!{\tbinom {k}{n}}\!{\big )}$. На пример, када је n = 3 и k = 2, торке које се броје по теореми су (3, 0), (2, 1), (1, 2), и (0, 3), и има их $\left(\!{\tbinom {3+1}{2-1}}\!\right)=4$.

Доказ помоћу методе звезда и линија

Прва теорема

Претпоставимо да постоји n објеката (представљених звијездама; у примеру испод n = 7) који се стављају у k посуда (у примеруk = 3), тако да све посуде садрже бар један објекат. Посуде се различите (рецимо нумерисане су од 1 до k ), али n звијезда су идентичне (тако да се конфигурације разликују само по броју звијезда присутних у свакој посуди). Конфигурација је тако представљена помоћу k-торки позитивних цијелих бројева, као у дефиницији теореме. Умјесто да почнемо са стављањем звијезда у посуде, почињемо тако што ћемо поставити звијезде у линију једну поред друге:

★ ★ ★ ★ ★ ★ ★

Fig. 1: седам објеката представљених помоћу звијезда

гдје ће се звијезде за прву посуду узети са лијеве стране, а затим звијезде за другу посуду, и тако даље. Тако ће се конфигурација одредити када се зна која је прва звијезда која иде у другу посуду, прва звијезда која иде у трећу посуду, и тако даље. Ово се може означити стављањем k − 1 усправних линија на мјестима између двије звезде. Пошто нити једна канта не смије да буде празна, може бити највише једана линије између датог пара звијезди:

★ ★ ★ ★

|

★

|

★ ★

Fig. 2: двије линије стварају три посуде које садрже 4, 1, и 2 објеката

Посматрајте n звијезда као фиксне објекте који дефинишу n − 1 празнина између звијезда, у сваком од њих може а и не мора бити једна линија (усправна линија раздвајања). Конфигурација се добија избором k − 1 ових празнина које заправо садржи линију; дакле, постоји ${\tbinom {n-1}{k-1}}$ могућих конфигурација (види комбинације).

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

У овом случају, приказ торки-а као низа звијезди и линија, са линијама које дијеле звијезде у посуде, је непромењен. Слабије ограничење ненегативности (умјесто позитивности) значи да се може поставити више линија између две звијезде, као и постављање линија пре прве звијезде или после последње звијезде. Тако, на пример, када је n = 7 и k = 5, торке (4, 0, 1, 2, 0) могу бити представљене следећим дијаграмом.

★ ★ ★ ★

|

|

★

|

★ ★

|

Fig. 3: четири линије стварају четири посуде са 4, 0, 1, 2, и 0 објеката

Овим се успоставља бијекција један-на-један између торки жељеног облика и селекције са заменом k − 1 празнине од n + 1 доступних празнина, или еквивалентно са (k − 1) елемената мулти сетова извучених из скупа величине n + 1. По дефиницији, такви објекти се броје помоћу вишеструког броја $\left(\!{\tbinom {n+1}{k-1}}\!\right)$.

Да бисмо видели да се ти објекти такође броје биномским коефицијентом ${\tbinom {n+k-1}{n}}$, приметите да се жељени распоред састоји од n + k − 1 објеката (n звијезда и k − 1 линија). Одабир позиција за звијезде оставља тачно k − 1 мјеста лијево за k − 1 линија. Односно, одабир позиција за звијезде одређује читав распоред, тако да се распоред одређује са ${\tbinom {n+k-1}{n}}$ избором. Напоменути да ${\tbinom {n+k-1}{n}}={\tbinom {n+k-1}{k-1}}$, што нам такође говори да је такође могуће одредити аранжман одабиром позиција за k − 1 линију.

Примјери

Ако n = 5, k = 4, и скуп величине k је {a, b, c, d}, тада ★|★★★||★ представља мултисет {a, b, b, b, d} или 4-торке(1, 3, 0, 1). Приказ било ког мултисета за овај примјер би користио n = 5 звијезда и k − 1 = 3 линија.

Многи проблеми у комбинаторици решавају се горенаведеним теоремама. На пример, ако неко жели да преброји број начина за дистрибуцију седам идентичних кованица од једног долара између Амбер, Бена и Кертиса тако да сваки од њих добије бар један долар, може се приметити да су дистрибуције у суштини еквивалентне торкама од три позитивна целе бројеве чија је сума 7. (Овде први унос у торку је број кованица дат Амбер, и тако даље). Тако се звијезде и линије могу примјенити са n = 7 и k = 3, и постоји $\textstyle {7-1 \choose 3-1}=15$ начина дистрибуције новчића.

Литература

• Pitman, Jim (1993). Probability. Berlin: Springer-Verlag. ISBN 978-0-387-97974-8. 
• Weisstein, Eric W. „Multichoose”. Mathworld -- A Wolfram Web Resource. Приступљено 18. 11. 2012.