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

С Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу

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

Дефиниције теорем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-торки позитивних цијелих бројева, као у дефиницији теореме. Умјесто да почнемо са стављањем звијезда у посуде, почињемо тако што ћемо поставити звијезде у линију једну поред друге:

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

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

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

Посматрајте n звијезда као фиксне објекте који дефинишу 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. По дефиницији, такви објекти се броје помоћу вишеструког броја .

Да бисмо видели да се ти објекти такође броје биномским коефицијентом , приметите да се жељени распоред састоји од n + k − 1 објеката (n звијезда и k − 1 линија). Одабир позиција за звијезде оставља тачно 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, и постоји начина дистрибуције новчића.

Референце[уреди | уреди извор]

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

Литература[уреди | уреди извор]

  • 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.