Zvijezde i linije (kombinatorika)

U kontekstu kombinatorne matematike, zvijezde i linije predstavljaju grafičku pomoć za izvođenje određenih kombinatornih teorema. Viliam Feler ga je popularizovao u svojoj klasičnoj knjizi o vjerovatnoći. Može da se koristiti za rješavanje mnogih jednostavnih problema brojanja, kao na primjer na koliko načina može da se raspodjeli n identičnih loptica u k različitih posuda.

Definicije teoreme

Metoda zvijezda i linija se često uvodi posebno da bi se dokazale sledeće dve teoreme elementarne kombinatorike.

Prva teorema

Za svaki par pozitivnih cijelih brojeva n i k, broj k-torki pozitivnih cijelih brojeva čija je suma n jednak je broju (k − 1) elemenata podskupa skupa sa n − 1 elementom.

Oba ova broja su predstavljena binomnim koeficijentom $\textstyle {n-1 \choose k-1}$. Na primer, kada je n = 3 i k = 2, torke koje se broje po teoremi su (2, 1) i (1, 2), i ima ih ${\tbinom {3-1}{2-1}}=2$.

Druga teorema

Za svaki par pozitivnih cijelih brojeva n i k, broj k-torki nenegativnih cijelih brojeva čija je suma n jednak je broju multisetova kardinalnosti k − 1 uzetih iz seta veliline n + 1.

Oba broja se dobijaju iz multiseta od $\left(\!{\tbinom {n+1}{k-1}}\!\right)$, ili ekvivalentno binomskim koeficijentom ${\tbinom {n+k-1}{k-1}}={\tbinom {n+k-1}{n}}$ ili multiset brojem ${\big (}\!{\tbinom {k}{n}}\!{\big )}$. Na primer, kada je n = 3 i k = 2, torke koje se broje po teoremi su (3, 0), (2, 1), (1, 2), i (0, 3), i ima ih $\left(\!{\tbinom {3+1}{2-1}}\!\right)=4$.

Dokaz pomoću metode zvezda i linija

Prva teorema

Pretpostavimo da postoji n objekata (predstavljenih zvijezdama; u primeru ispod n = 7) koji se stavljaju u k posuda (u primeruk = 3), tako da sve posude sadrže bar jedan objekat. Posude se različite (recimo numerisane su od 1 do k ), ali n zvijezda su identične (tako da se konfiguracije razlikuju samo po broju zvijezda prisutnih u svakoj posudi). Konfiguracija je tako predstavljena pomoću k-torki pozitivnih cijelih brojeva, kao u definiciji teoreme. Umjesto da počnemo sa stavljanjem zvijezda u posude, počinjemo tako što ćemo postaviti zvijezde u liniju jednu pored druge:

★ ★ ★ ★ ★ ★ ★

Fig. 1: sedam objekata predstavljenih pomoću zvijezda

gdje će se zvijezde za prvu posudu uzeti sa lijeve strane, a zatim zvijezde za drugu posudu, i tako dalje. Tako će se konfiguracija odrediti kada se zna koja je prva zvijezda koja ide u drugu posudu, prva zvijezda koja ide u treću posudu, i tako dalje. Ovo se može označiti stavljanjem k − 1 uspravnih linija na mjestima između dvije zvezde. Pošto niti jedna kanta ne smije da bude prazna, može biti najviše jedana linije između datog para zvijezdi:

★ ★ ★ ★

|

★

|

★ ★

Fig. 2: dvije linije stvaraju tri posude koje sadrže 4, 1, i 2 objekata

Posmatrajte n zvijezda kao fiksne objekte koji definišu n − 1 praznina između zvijezda, u svakom od njih može a i ne mora biti jedna linija (uspravna linija razdvajanja). Konfiguracija se dobija izborom k − 1 ovih praznina koje zapravo sadrži liniju; dakle, postoji ${\tbinom {n-1}{k-1}}$ mogućih konfiguracija (vidi kombinacije).

Druga teorema

U ovom slučaju, prikaz torki-a kao niza zvijezdi i linija, sa linijama koje dijele zvijezde u posude, je nepromenjen. Slabije ograničenje nenegativnosti (umjesto pozitivnosti) znači da se može postaviti više linija između dve zvijezde, kao i postavljanje linija pre prve zvijezde ili posle poslednje zvijezde. Tako, na primer, kada je n = 7 i k = 5, torke (4, 0, 1, 2, 0) mogu biti predstavljene sledećim dijagramom.

★ ★ ★ ★

|

|

★

|

★ ★

|

Fig. 3: četiri linije stvaraju četiri posude sa 4, 0, 1, 2, i 0 objekata

Ovim se uspostavlja bijekcija jedan-na-jedan između torki željenog oblika i selekcije sa zamenom k − 1 praznine od n + 1 dostupnih praznina, ili ekvivalentno sa (k − 1) elemenata multi setova izvučenih iz skupa veličine n + 1. Po definiciji, takvi objekti se broje pomoću višestrukog broja $\left(\!{\tbinom {n+1}{k-1}}\!\right)$.

Da bismo videli da se ti objekti takođe broje binomskim koeficijentom ${\tbinom {n+k-1}{n}}$, primetite da se željeni raspored sastoji od n + k − 1 objekata (n zvijezda i k − 1 linija). Odabir pozicija za zvijezde ostavlja tačno k − 1 mjesta lijevo za k − 1 linija. Odnosno, odabir pozicija za zvijezde određuje čitav raspored, tako da se raspored određuje sa ${\tbinom {n+k-1}{n}}$ izborom. Napomenuti da ${\tbinom {n+k-1}{n}}={\tbinom {n+k-1}{k-1}}$, što nam takođe govori da je takođe moguće odrediti aranžman odabirom pozicija za k − 1 liniju.

Primjeri

Ako n = 5, k = 4, i skup veličine k je {a, b, c, d}, tada ★|★★★||★ predstavlja multiset {a, b, b, b, d} ili 4-torke(1, 3, 0, 1). Prikaz bilo kog multiseta za ovaj primjer bi koristio n = 5 zvijezda i k − 1 = 3 linija.

Mnogi problemi u kombinatorici rešavaju se gorenavedenim teoremama. Na primer, ako neko želi da prebroji broj načina za distribuciju sedam identičnih kovanica od jednog dolara između Amber, Bena i Kertisa tako da svaki od njih dobije bar jedan dolar, može se primetiti da su distribucije u suštini ekvivalentne torkama od tri pozitivna cele brojeve čija je suma 7. (Ovde prvi unos u torku je broj kovanica dat Amber, i tako dalje). Tako se zvijezde i linije mogu primjeniti sa n = 7 i k = 3, i postoji $\textstyle {7-1 \choose 3-1}=15$ načina distribucije novčića.

Literatura

• Pitman, Jim (1993). Probability. Berlin: Springer-Verlag. ISBN 978-0-387-97974-8. 
• Weisstein, Eric W. „Multichoose”. Mathworld -- A Wolfram Web Resource. Pristupljeno 18. 11. 2012.