Pike in pregrade (kombinatorika): Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
Ustvarjeno s prevodom strani »Stars and bars (combinatorics)« |
Oznaka: Izboljšani urejevalnik wikikode |
||
Vrstica 30:
=== 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||
|col3align=center||
|col4align=center|★
|col5align=center||
|col6align=left|★ ★
|col7align=center||
}}
|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'' − 1|size=100%}} prostih mest izmed {{Matematična formula|''n'' + 1|size=100%}} le-teh. Ekvivalentno: ({{Matematična formula|''k'' − 1|size=100%}})-elementne ''večkratne množice'' iz množice velikosti {{Matematična formula|''n'' + 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'' − 1}} teles (''n'' pik in {{Matematična formula|''k'' − 1}} pregrad). Z izbiro položaja pik dobimo natanko {{Matematična formula|''k'' − 1}} praznih mest za {{Matematična formula|''k'' − 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'' − 1}} pregrad.
| |||