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

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

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

<blockquote>
За сваки пар [[Природан број|позитивних цијелих бројева]] ''n'' и ''k'', број ''k''-торки '''позитивних''' цијелих бројева чија је сума ''n'' једнак је броју (''k'' − 1) елемената подскупа скупа са ''n'' − 1 елементом.
</blockquote>

Оба ова броја су представљена [[Биномни коефицијент|биномним коефицијентом]] <math>\textstyle{n - 1\choose k-1}</math>. На пример, када је ''n'' = 3 и ''k'' = 2, торке које се броје по теореми су (2, 1) и (1, 2), и има их <math> \tbinom{3 - 1}{2 - 1} = 2</math>.

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

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

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

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

=== Прва теорема ===

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

{{image frame
|width=250
|align=center
|content=
{{Aligned table
|style=font-size:180%;
|★  ★  ★  ★  ★  ★  ★
}}
|caption=Fig. 1: седам објеката представљених помоћу звијезда 
}}

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

{{image frame
|width=250
|align=center
|content=
{{Aligned table
|style=font-size:180%;
| cols=5
| col1align=right | ★  ★  ★  ★
| col2align=center | &#124;
| col3align=center | ★
| col4align=center | &#124;
| col5align=left | ★  ★
}}
|caption=Fig. 2: двије линије стварају три посуде које садрже 4, 1, и 2 објеката
}}

Посматрајте ''n'' звијезда као фиксне објекте који дефинишу {{math|''n''&nbsp;−&nbsp;1}} празнина између звијезда, у сваком од њих може а и не мора бити једна линија (усправна линија раздвајања). Конфигурација се добија избором {{math|''k''&nbsp;−&nbsp;1}} ових празнина које заправо садржи линију; дакле, постоји <math>\tbinom{n - 1}{k - 1}</math> могућих конфигурација (види [[Комбинација|комбинације]]).

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

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

{{image frame
|width=300
|align=center
|content=
{{Aligned table
|style=font-size:180%;
|cols=7
|col1align=right|★  ★  ★  ★
|col2align=center|&#124;
|col3align=center|&#124;
|col4align=center|★
|col5align=center|&#124;
|col6align=left|★  ★
|col7align=center|&#124;
}}
|caption=Fig. 3: четири линије стварају четири посуде са 4, 0, 1, 2, и 0 објеката
}}

Овим се успоставља [[бијекција]] један-на-један између торки жељеног облика и селекције са заменом {{math|size=100%|''k''&nbsp;−&nbsp;1}} празнине од {{math|size=100%|''n''&nbsp;+&nbsp;1}} доступних празнина, или еквивалентно са ({{math|size=100%|''k''&nbsp;−&nbsp;1}}) елемената мулти сетова извучених из скупа величине {{math|size=100%|''n''&nbsp;+&nbsp;1}}. По дефиницији, такви објекти се броје помоћу вишеструког броја <math>\left(\!\tbinom{n + 1}{k - 1}\!\right)</math>.

Да бисмо видели да се ти објекти такође броје биномским коефицијентом <math>\tbinom{n + k - 1}{n}</math>, приметите да се жељени распоред састоји од {{math|size=100%|''n'' + ''k''&nbsp;−&nbsp;1}} објеката (''n'' звијезда и {{math|size=100%|''k''&nbsp;−&nbsp;1}} линија). Одабир позиција за звијезде оставља тачно {{math|size=100%|''k''&nbsp;−&nbsp;1}} мјеста лијево за {{math|size=100%|''k''&nbsp;−&nbsp;1}} линија. Односно, одабир позиција за звијезде одређује читав распоред, тако да се распоред одређује са <math>\tbinom{n + k - 1}{n}</math> избором. Напоменути да <math>\tbinom{n + k - 1}{n} = \tbinom{n + k - 1}{k - 1}</math>, што нам такође говори да је такође могуће одредити аранжман одабиром позиција за {{math|size=100%|''k''&nbsp;−&nbsp;1}} линију.

== Примјери ==

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

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

== Референце ==
{{reflist|30em}}

== Литература ==
* {{Cite book | ref = harv | last=Pitman |first=Jim |title=Probability | url = https://archive.org/details/probability0000pitm |publisher=Springer-Verlag |location=Berlin |year=1993 |isbn=978-0-387-97974-8 |oclc= |doi=| pages =  }}
* {{cite web|last=Weisstein|first=Eric W.|title=Multichoose|url=http://mathworld.wolfram.com/Multichoose.html|work=Mathworld -- A Wolfram Web Resource|accessdate=18. 11. 2012}}

{{нормативна контрола}}

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