Ogled vira Pike in pregrade (kombinatorika)

'''Pike in pregrade''' ([[angleško]] '''stars and bars''') so v [[Kombinatorika|kombinatorični matematiki]] grafična pomoč pri izpeljavi določenih [[Kombinatorika|kombinatoričnih]] izrekov. Populariziral jo je [[William Feller]] v svoji knjigi o [[Verjetnost|verjetnosti]]. Uporablja se za reševanje veliko preprostih [[Preštevalna kombinatorika|problemov preštevanja]], kot recimo: koliko je načinov, da razvrstimo ''n'' enakih krogel v ''k'' enakih posod.<ref>{{Navedi knjigo|last=Feller|first=William|authorlink=William Feller|year=1950|title=An Introduction to Probability Theory and Its Applications|publisher=Wiley|volume=1|edition=2.}}</ref>

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

=== 1. izrek ===
<blockquote>
Za katerikoli par [[Naravno število|naravnih števil]] ''n'' in ''k'', je število ''k''-[[Urejena množica|urejenih množic]] '''naravnih''' števil, katerih vsota je enaka ''n,'' enako številu (''k'' − 1)-elementni podmnožici množice z ''n'' − 1 elementi.
</blockquote>Obe števili sta podani z [[Binomski koeficient|binomskim koeficientom]] <math>\textstyle{n - 1\choose k-1}</math>. 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 <math> \tbinom{3 - 1}{2 - 1} = 2</math> takšnih množic.

=== 2. izrek ===
<blockquote>
Za katerikoli par naravnih števil ''n'' in ''k'', je število ''k''-[[Relacija urejenosti|urejenih množic]] '''nenegativnih''' celih števil, katerih vsota je ''n'', enako številu [[Večkratna množica|večkratnih množic]] [[Kardinalnost|kardinalnosti]] ''k'' − 1, ki jih vzamemo iz množice velikosti ''n'' + 1.
</blockquote>Obe števili sta podani s [[Večkratna množica|številom večkratne množice]] <math>\left(\!\tbinom{n + 1}{k - 1}\!\right)</math>, ali ekvivalentno z binomskim koeficientom <math>\tbinom{n + k - 1}{k - 1} = \tbinom{n + k - 1}{n}</math> ali številom večkratne množice <math>\big(\!\tbinom{k}{n}\!\big)</math>. 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 <math>\left(\!\tbinom{3 + 1}{2 - 1}\!\right) = 4</math>.

== 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.{{Okvirslike|width=250|align=center|content={{huge
|★  ★  ★  ★  ★  ★  ★
}}|caption=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 {{Matematična formula|''k''&nbsp;−&nbsp;1}} ločitvenih '''pregrad''' med dvema pikama. Ker ne sme biti nobena posoda prazna, je lahko med dvema pikama največ ena pregrada:{{Okvirslike|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: dve pregradi podata konfiguracijo s tremi posodami, ki vsebujejo zaporedoma 4, 1 in 2 telesi}}Poglejmo na ''n'' zvezd kot stalne objekte, ki definirajo {{Matematična formula|''n''&nbsp;−&nbsp;1}} prostih mest med zvezdami, v katerih je lahko ali pa ni ena pregrada (razdeljevanje na posode). Konfiguracijo se dobi z izbiro {{Matematična formula|''k''&nbsp;−&nbsp;1}} teh prostih mest, ki bodo dejansko vsebovala pregrado. Iz tega sledi, da je <math>\tbinom{n - 1}{k - 1}</math> možnih konfiguracij (glej [[Kombinacija (matematika)|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.
{{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: štiri pregrade podajo pet posod, ki vsebujejo zaporedno 4, 0, 1, 2 in 0 teles
}}
To vzpostavi [[Bijektivna preslikava|bijekcijo]] med urejenimi množicami želene oblike in izbirami z zamenjavo {{Matematična formula|''k''&nbsp;−&nbsp;1|size=100%}} prostih mest izmed {{Matematična formula|''n''&nbsp;+&nbsp;1|size=100%}} le-teh. Ekvivalentno: ({{Matematična formula|''k''&nbsp;−&nbsp;1|size=100%}})-elementne ''večkratne množice'' iz množice velikosti {{Matematična formula|''n''&nbsp;+&nbsp;1|size=100%}}. Po definiciji se takšni objekti štejejo iz števila večkratnih množic <math>\left(\!\tbinom{n + 1}{k - 1}\!\right)</math>.

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

== Primeri ==
Za ''n''&nbsp;=&nbsp;5, ''k''&nbsp;=&nbsp;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''&nbsp;−&nbsp;1 = 3 pregrad.

Veliko elementarnih [[Besedilna naloga (matematično izobraževanje)|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 <math>\textstyle{7-1 \choose 3-1} = 15</math> možnih načinov za porazdelitev kovancev.

== Glej tudi ==

* [[Particija (teorija števil)]]

== Sklici ==
<references />

== Nadaljnje branje ==

* {{Navedi knjigo|last=Pitman|first=Jim|year=1993|title=Probability|url=https://archive.org/details/probability0000pitm|publisher=Springer-Verlag|location=Berlin|isbn=0-387-97974-3}}
* {{Navedi splet|last=Weisstein|first=Eric W.|title=Multichoose|website=Mathworld -- A Wolfram Web Resource|url=http://mathworld.wolfram.com/Multichoose.html|accessdate=18 November 2012}}
[[Kategorija:Kombinatorika]]