Pike in pregrade (kombinatorika)

Pike in pregrade (angleško stars and bars) so v kombinatorični matematiki grafična pomoč pri izpeljavi določenih kombinatoričnih izrekov. Populariziral jo je William Feller v svoji knjigi o verjetnosti. Uporablja se za reševanje veliko preprostih problemov preštevanja, kot recimo: koliko je načinov, da razvrstimo n enakih krogel v k enakih posod.

Izreki

Metoda pik in pregrad se pogosto uporablja za dokaz sledečih dveh izrekov elementarne kombinatorike.

1. izrek

Za katerikoli par naravnih števil n in k, je število k-urejenih množic naravnih števil, katerih vsota je enaka n, enako številu (k − 1)-elementni podmnožici množice z n − 1 elementi.

Obe števili sta podani z binomskim koeficientom $\textstyle {n-1 \choose k-1}$. Ko je na primer n = 3 in k = 2, sta urejeni množici, ki jih šteje izrek, enaki (2, 1) in (1, 2), obstaja pa natanko ${\tbinom {3-1}{2-1}}=2$ takšnih množic.

2. izrek

Za katerikoli par naravnih števil n in k, je število k-urejenih množic nenegativnih celih števil, katerih vsota je n, enako številu večkratnih množic kardinalnosti k − 1, ki jih vzamemo iz množice velikosti n + 1.

Obe števili sta podani s številom večkratne množice $\left(\!{\tbinom {n+1}{k-1}}\!\right)$, ali ekvivalentno z binomskim koeficientom ${\tbinom {n+k-1}{k-1}}={\tbinom {n+k-1}{n}}$ ali številom večkratne množice ${\big (}\!{\tbinom {k}{n}}\!{\big )}$. Za n = 3 in k = 2 so urejeni pari, ki jih šteje izrek, enaki (3, 0), (2, 1), (1, 2) in (0, 3). Takih urejenih parov je $\left(\!{\tbinom {3+1}{2-1}}\!\right)=4$.

Dokazi z metodo pik in pregrad

1. izrek

Naj je n teles (ki jih tu predstavljajo pike; v primeru spodaj n = 7) položenih v k posod (v tem primeru k = 3), tako da vse posode vsebujejo najmanj eno telo. Posode so prepoznavne (recimo da so oštevilčene od 1 do k), toda n pik ni (torej se konfiguracije razlikujejo le po številu pik, ki so v posamezni posodi). Konfiguracija je torej predstavljena s k-urejeno množico naravnih števil, kot v matematičnem izrazoslovju izreka. Namesto da polagamo pike v posode, najprej položimo pike v vrsto.

★ ★ ★ ★ ★ ★ ★

Fig. 1: sedem teles, ki jih predstavljajo zvezde

kjer bodo pike z leve šle v prvo posodo, sledile jim bodo pike za v drugo posodo in tako naprej. Iz tega sledi, da bo konfiguracija znana, ko bo znana prva pika, ki bo šla v drugo posodo in prva pika, ki bo šla v tretjo posodo in tako naprej. To se lahko označi s polaganjem k − 1 ločitvenih pregrad med dvema pikama. Ker ne sme biti nobena posoda prazna, je lahko med dvema pikama največ ena pregrada:

★ ★ ★ ★

|

★

|

★ ★

Fig. 2: dve pregradi podata konfiguracijo s tremi posodami, ki vsebujejo zaporedoma 4, 1 in 2 telesi

Poglejmo na n zvezd kot stalne objekte, ki definirajo n − 1 prostih mest med zvezdami, v katerih je lahko ali pa ni ena pregrada (razdeljevanje na posode). Konfiguracijo se dobi z izbiro k − 1 teh prostih mest, ki bodo dejansko vsebovala pregrado. Iz tega sledi, da je ${\tbinom {n-1}{k-1}}$ možnih konfiguracij (glej kombinacije).

2. izrek

V tem primeru je predstavitev urejene množice kot zaporedja pik in pregrad nespremenjena, saj pregrade še vedno delijo pike v posode. Edin pogoj, ki ga bomo spremenili, je ta, da je lahko na enem prostem mestu tudi več pregrad, ki pa jih lahko postavimo tudi pred prvo in za zadnjo piko. Ko je n = 7 in k = 5, se lahko urejena množica (4, 0, 1, 2, 0) predstavi v sledečem diagramu.

★ ★ ★ ★

|

|

★

|

★ ★

|

Fig. 3: štiri pregrade podajo pet posod, ki vsebujejo zaporedno 4, 0, 1, 2 in 0 teles

To vzpostavi bijekcijo med urejenimi množicami želene oblike in izbirami z zamenjavo k − 1 prostih mest izmed n + 1 le-teh. Ekvivalentno: (k − 1)-elementne večkratne množice iz množice velikosti n + 1. Po definiciji se takšni objekti štejejo iz števila večkratnih množic $\left(\!{\tbinom {n+1}{k-1}}\!\right)$.

Zgoraj dobljeni rezultat lahko izrazimo tudi kot ${\tbinom {n+k-1}{n}}$. Da bi to lahko dobili tudi po drugi poti, moramo videti, da je želena konfiguracija sestavljena iz n + k − 1 teles (n pik in k − 1 pregrad). Z izbiro položaja pik dobimo natanko k − 1 praznih mest za k − 1 pregrad. Z izbiro položaja pik, ki ga določa celotna razporeditev, dobimo ${\tbinom {n+k-1}{n}}$ izbir. Toda velja ${\tbinom {n+k-1}{n}}={\tbinom {n+k-1}{k-1}}$, kar je posledica tega, da se lahko enak rezultat dobi z izbiro k − 1 pregrad.

Primeri

Za n = 5, k = 4 in za množico velikosti k, ki je {a, b, c, d}, bi ★|★★★||★ predstavljalo večkratno množico {a, b, b, b, d} ali 4-urejeno množico (1, 3, 0, 1). Predstavitev katerekoli večkratne množice za ta primer bi uporabljala n = 5 pik in k − 1 = 3 pregrad.

Veliko elementarnih besedilnih nalog v kombinatoriki se da rešiti z zgornjima izrekoma. Če želi nekdo prešteti število načinov za razporeditev sedem enakih evrskih kovancev med Anžeta, Benjamina in Ceneta, da vsak dobi najmanj en evro, lahko opazi, da so porazdelitve kovancev enake urejenim množicam treh naravnih števil, katerih vsota je enaka 7. (Prva vrednost je število Anžetovih kovancev in tako naprej.) Tukaj lahko uporabimo pike in pregrade z n = 7 in k = 3 in dobimo $\textstyle {7-1 \choose 3-1}=15$ možnih načinov za porazdelitev kovancev.

Glej tudi

• Particija (teorija števil)

Nadaljnje branje

• Pitman, Jim (1993). Probability. Berlin: Springer-Verlag. ISBN 0-387-97974-3.
• Weisstein, Eric W. »Multichoose«. Mathworld -- A Wolfram Web Resource. Pridobljeno 18. novembra 2012.