У контексту комбинаторне математике, звијезде и линије представљају графичку помоћ за извођење одређених комбинаторних теорема. Вилиам Фелер га је популаризовао у својој класичној књизи о вјероватноћи. Може да се користити за рјешавање многих једноставних проблема бројања, као на примјер на колико начина може да се расподјели n идентичних лоптица у k различитих посуда.Feller, W. (1950) An Introduction to Probability Theory and Its Applications, Wiley, Vol 1, 2nd ed.

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

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

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

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

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

Оба броја се добијају из мултисета од , или еквивалентно биномским коефицијентом или мултисет бројем . На пример, када је n = 3 и k = 2, торке које се броје по теореми су (3, 0), (2, 1), (1, 2), и (0, 3), и има их .

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

Прва теорема

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

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

Посматрајте n звијезда као фиксне објекте који дефинишу празнина између звијезда, у сваком од њих може а и не мора бити једна линија (усправна линија раздвајања). Конфигурација се добија избором ових празнина које заправо садржи линију; дакле, постоји могућих конфигурација (види комбинације).

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

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

Овим се успоставља бијекција један-на-један између торки жељеног облика и селекције са заменом празнине од доступних празнина, или еквивалентно са () елемената мулти сетова извучених из скупа величине . По дефиницији, такви објекти се броје помоћу вишеструког броја .

Да бисмо видели да се ти објекти такође броје биномским коефицијентом , приметите да се жељени распоред састоји од објеката (n звијезда и линија). Одабир позиција за звијезде оставља тачно мјеста лијево за линија. Односно, одабир позиција за звијезде одређује читав распоред, тако да се распоред одређује са избором. Напоменути да , што нам такође говори да је такође могуће одредити аранжман одабиром позиција за линију.

Примјери

Ако 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, и постоји начина дистрибуције новчића.

Референце

Литература

Категорија:Комбинаторика