Kombinatorika

Teória partícií predstavuje jednu z najpozoruhodnejších častí klasickej kombinatoriky. V tomto odseku ukážeme len niekoľko zaujímavých výsledkov.

Partícia prirodzeného čísla $n$ sa nazýva vyjadrenie čísla $n$ v tvare súčtu nenulových prirodzených čísel 
$n=a_1+a_2+ \cdot \cdot \cdot +a_r$.

Obyčajne sa pri štúdiu partícií rozlišujú dva prípady. Partície, v ktorých 

1. záleží na poradí sčítancov $a_1,a_2, \cdot \cdot \cdot ,a_r$, napríklad partície $2+3 ,\; \;3+2$ čísla $6$ budeme považovať za rôzne
2. nezáleží na poradí sčítancov $a_1,a_2, \cdot \cdot \cdot ,a_r$, napríklad partície $1+2+3 ,\; \;3+1+2$ budeme považovať totožné

Budeme skúmať len prvý prípad. Dve partície líšiace sa len poradím sčítancov považujeme za rôzne. Označme počet všetkých takýchto partícií čísla $n$ pozostávajúcich z presne $r$ sčítancov $(r \leq n)$ symbolom
$\small  P(n,r)$.
V ďalšom sa budeme snažiť určiť číslo $\small  P(n,r)$.

Nakreslime na priamke vedľa seba $n$ bodov. Medzi nimi máme $(n-1)$ medzier a zvoľme z nich $(r-1)$ medzier. Táto voľba sa dá zrejme uskutočniť
$\small  C(n-1,r-1)$
spôsobmi. Vložme do nich zvislé čiarky. Napr.: Rozdeliť číslo 6 na 4 časti znamená zvoliť 3 medzery z 5.

Tým sa pôvodných $n$ bodov rozdelí na $r$ častí, pričom rôznym voľbám $(r-1)$ medzier zodpovedajú rôzne rozdelenia (aspoň čo do poradia ), čiže partícií čísla $n$ na $r$ častí. Dokázali sme vlastne vetu o počte partícií.

Veta o počte partícií.
Počet partícií (navzájom rôznych aspoň poradím) čísla $n$ na $r$ častí sa rovná
$\small  P(n,r)=C(n-1,r-1)$

Príklad. Rozklad čísla $\small  6$ na $\small  3$ nenulových sčítancov. Vypíšte všetky rozklady.
Riešenie. Číslo $\small  6$ má $\small  P(6,3)=C(6-1,3-1)=C(5,2)=10$ partícií z troch sčítancov. Sú to partície:
$\small  1 + 2 + 3, \; \;2 + 1 + 3,\; \; 1 + 3 + 2,\; \; 3 + 1 + 2,\; \; 2 + 3 + 1,\; \;3 + 2 + 1$
$\small  1 + 1 + 4, \; \; 1 + 4 + 1, \; \; 4 + 1 + 1, \; \; 2 + 2 + 2$.  Otvorte si applet Tu.

Teraz už ľahko určíme počet všetkých rôznych (aspoň) poradím partícií čísla $n$.

Ak si to číslo označíme symbolom $\small  P(n)$, tak zrejme platí
$\small  P(n)=P(n,1)+P(n,2)+ \cdot \cdot \cdot +P(n,n)$.
Použitím vety a identity
$\sum_{k=0}^{n}{ \binom {n} {k} =2n}$
potom dostávame
$\small  P(n) =2n-1$.

Úloha.
Koľkými spôsobmi môžeme urobiť nákup, ktorý pozostáva zo 5 litrov mlieka, ak v obchode majú tri druhy mlieka -nízkotučné, polotučné a plnotučné. V nákupe musia byť zastúpené všetky druhy mlieka. Podmienka: nákup musí obsahovať z každého druhu aspoň jeden liter mlieka. Vypíšte všetky možnosti nákupu.
Návod.

• Označme si nákup ako usporiadanú trojicu prirodzených čísel $(n,p,t)$, kde jednotlivé čísla predstavujú koľko litrov sme nakúpili z daného druhu mlieka.
• Napríklad trojica $\small  (1,1,2)$ predstavuje nákup 1 litra nízkotučného mlieka a 1 litre polotučného a 2 litre plnotučného mlieka, preto nespĺňa podmienku nákupu.
• Trojica $\small  (1,2,2)$ predstavuje nákup 1 litra nízkotučného mlieka a 2 litre polotučného a 2 litre plnotučného mlieka, preto spĺňa podmienku nákupu.
• Trojica $\small  (3,2,0)$ nepredstavuje nákup, keďže neobsahuje plnotučné mlieko.
• Nákup zrejme predstavuje partície - rozklad čísla 5 na tri nenulové sčítance. Vymenovaním všetkých partícií zistíme, že ich je práve 6.
• Vypíšte všetky 6 partície. Otvorte tabuľu Tu.

Zrejme pri tomto nákupe nezáleží na poradí a zároveň platí, že neobsahujú nulový prvok (každý druh mlieka musí byť zastúpený).
Tieto podmienky spĺňa zadanie našej úlohy. Sú to teda partície z 5 prvkov a 3 triedy. Pre počet všetkých platí
$\small  P(5,3)=C(5-1,3-1)=C(4,2)=6$.