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 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é

Začneme prvým prípadom. 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
$P(n,r)$.
V ďalšom sa budeme snažiť určiť číslo $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ť
$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á
$P(n,r)=C(n-1,r-1)$

Príklad. Rozklad čísla $6$ na $3$ nenulových sčítancov. Vypíšte všetky rozklady.
Riešenie. Číslo $6$ má $P(6,3)=C(6-1,3-1)=C(5,2)=10$ partícií z troch sčítancov. Sú to partície:
$1 + 2 + 3, \; \;2 + 1 + 3,\; \; 1 + 3 + 2,\; \; 3 + 1 + 2,\; \; 2 + 3 + 1,\; \;3 + 2 + 1$
$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 $P(n)$, tak zrejme platí
$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
$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. 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 $(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 $(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.
• Nákup predstavuje partície, v ktorých záleží na poradí. 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í
$P(5,3)=C(5-1,3-1)=C(4,2)=6$.