Kombinatorika

Nech $\small{M_n}= \lbrace{a_1,a_2, \cdot \cdot \cdot ,a_n}\rbrace$ je množina $n$ kategórií (druhov, prvkov). Vytvorme $r$-tice z prvkov týchto kategórií, v ktorých nezáleží na poradí ale prvky (prvky zo zvoleného druhu) sa môžu opakovať. Zrejme môže nastať aj prípad $r \geq n$.
Ukážka
K dispozícii máme dostatočný počet farebných štítkov: modré $m$, červené $č$, žlté $ž$ a zelené $z$, teda máme  $\small n=4$ druhy. Vypíšte niektoré možnosti výberu troch štítkov, teda $\small r=3$. Vo výbere sa môžu vyskytovať  štítky rovnakej farby. Avšak nemusí byť každá farba zastúpená vo výbere. Využite nasledujúci applet.

Definícia.
$r$-kombinácie s opakovaním definujeme ako $r$-tice prvkov z $n$ druhov $\small   \lbrace{a_1,a_2, \cdot \cdot \cdot ,a_n}\rbrace$, v ktorých nezáleží na poradí ale prvky (druhy) sa môžu opakovať. Počet všetkých $r$-kombinácií s opakovaním z $n$ prvkov budeme označovať symbolom $\small  C'(n,r)$.

Kombinácia s opakovaním $\small  a_1 a_2 \cdot \cdot \cdot a_r$ bude ľubovoľná (neusporiadaná) $r$-tica prvkov z množiny $\small{M_n}= \lbrace{a_1,a_2, \cdot \cdot \cdot ,a_n}\rbrace$.

• Výber $r$-tica predpokladá, že prvkov každého druhu $\small   a_i \in M_n$ je dostatočne veľa, teda aspoň $r$.
• Pri určovaní počtu všetkých $r$-kombinácií s opakovaním z $n$ prvkov budeme využívať výsledky, ktoré sme odvodili pri partíciách a pri skúmaní vlastností permutácií s opakovaním.

Príklad.
V obchode predávajú tri druhy cukru: kryštálový $k$, práškový $p$ a hnedý $h$ v kilogramovom balení, teda $n=3$ . Vypíšte všetky možnosti pri nákupe 2 resp. 3 kilogramov cukru, teda $r=2$ resp. $r=3$. V nákupe sa môže opakovať ten istý druh cukru avšak nemusí byť každý druh cukru zastúpený v nákupe.

Riešenie.
Uvedieme nejaké možné nákupy, napríklad 2 kilogramový nákup môže byť {1 kg práškového cukru, 1 kg kryštálového cukru} $\equiv \lbrace{p,k}\rbrace = \lbrace{k,p}\rbrace$ alebo 3 kilogramový nákup môže byť {2 kg práškového cukru, 1 kg hnedého cukru} $\equiv \lbrace{p,p,h}\rbrace = \lbrace{p,h,p}\rbrace$.
Všetky nákupy dvoch kilogramov budú predstavovať 2-kombinácie s opakovaním z troch druhov cukru - $\small   C'(3,2)$. Všetky nákupy troch kilogramov budú predstavovať 3-kombinácie s opakovaním z troch druhov cukru - $\small   C'(3,3)$.
Pokúste sa vymenovať všetky možné nákupy. Pri nákupe

1. dvoch kilogramov máme 6 možností ... vypíšte ich.  Obr. Tu.
2. troch kilogramov dostaneme 10 možností... výpočet Tu.

Veta.
Pre počet $r$-kombinácií s opakovaním z $n$ druhov platí
$\small   C'(n,r)=C(n+r-1,n-1)$.

Dôkaz.
Nech $\small   x_i$ označuje počet výskytu prvku $\small   a_i \in M_n$ v nejakej $r$-kombinácií $\small   a_1 a_2 \cdot \cdot \cdot a_r$ s opakovaním. Potom zrejme musí platiť rovnosť
     [1] $x_1+x_2+ \cdot \cdot \cdot + x_n=r$.             [Napríklad pre nákup $\small  \lbrace{k,p}\rbrace$ ide o rovnosť $\small   1+1+0=2$.]
Ak k obidvom stranám rovnosti [1] pripočítame číslo $n$, tak po úprave dostaneme rovnosť
     [2] $y_1+y_2+ \cdot \cdot \cdot + y_n=r+n$       [Pre nákup $\small  \lbrace{k,p}\rbrace$ ide o rovnosť $\small   2+2+1=5$.]
kde $y_i =x_i +1$ pre $i=1,2, \cdot \cdot \cdot ,n$.  
Na rovnosť $\small  y_1+y_2+ \cdot \cdot \cdot + y_n=r+n$ sa môžeme pozerať ako na rozdelenie čísla $r+n$ na $n$ častí alebo ako na partície (navzájom rôznych aspoň poradím) čísla $r+n$ na $n$ častí.
Počet takýchto partícií je rovný číslu
     [3]$\small   P(n+r,n)=C(n+r-1,n-1)$. Tým sme dokázali tvrdenie. Na ilustráciu dôkazu použite applet:
Pre nákup štyroch kg cukru dostávame $\small   C(4+3-1,3-1)=15$ Vypíšte všetky 4-kombinácie..

Iný spôsob určovania počtu kombinácií s opakovaním budeme prezentovať na úlohe:
"V obchode majú tri druhy sirupu: jahodový, malinový a pomarančový. Určte počet všetkých možností nákupu piatich fliaš sirupu v obchode."

Úlohu vyriešime tak, že najskôr navrhneme spôsob, ako rozmiestniť $\small r=5$ fliaš sirupu do $\small n=3$ druhov/košov. Použijeme dva symboly: • fľaša; ↑ oddeľovač.

• Ak vložíme jeden oddeľovač medzi fľaše, tak to bude znamenať, že sme fľaše rozdelili na dve podmnožiny resp. že sme ich umistnili do dvoch rôznych košov.
• Ak umiestnime dva oddeľovače medzi fľaše, tak to bude znamenať, že sme fľaše rozdelili na tri podmnožiny (môže nastať aj prípad prázdnej podmnožiny) resp. že sme ich umistnili do troch rôznych košov.

Vo všeobecnosti rozmiestnenia budú predstavovať $\small (r+n−1)$-tice, v ktorých sa

1. (počet prvkov kombinácie - fľaše) symbol "•" sa vyskytuje $\small r$-krát
2. (počet oddeľovačov = počet druhov zmenšený o 1) symbol "↑" sa vyskytuje $\small n-1$-krát. 

Pri rozmiestnení záleží na poradí, preto sú to permutácie dvoch prvkov (fľaše + oddeľovače) s opakovaním. V našom príklade bude počet takých $\small (5+3-1)$-tíc zodpovedať počtu permutácií zo 7 prvkov s opakovaním, kde sa prvý prvok opakuje/vyskytuje $\small 5$-krát a druhý $\small (3-1)$-krát.  
$\small P'(5,2)=\large \frac{ (5+(3-1))!}{5!2! }$=$\small , C'(5+2,2)=21$.

Cvičenie 1.
Vyriešte týmto spôsobom predchádzajúcu úlohu o nákupe cukru.

Cvičenie 2.
Vyriešte obidvoma spôsobmi úlohu o počte farebných štítkov.

 
Vľavo je použitý 1. spôsob pomocou partícií a vpravo 2. spôsob popmocou permutáciií.