Kombinatorika

Definícia.
Permutácie s opakovaním z $n$ prvkov je usporiadaná $k$-tica zostavená z týchto prvkov tak, že každý sa v nej vyskytuje aspoň raz.

Vzťah medzi $k$ a $n$ je nasledujúci:
Prirodzené číslo $n$ udáva počet rôznych prvkov. Jednotlivé prvky sa môžu opakovať. Je zvykom označovať

• počet opakovaní prvého prvku $k_1$
• počet opakovaní druhého prvku $k_2$
a tak ďalej, až
• počet opakovaní posledného prvku $k_n$

Prirodzené číslo $k$ označuje počet všetkých prvkov, ktorých rôzne poradie skúmame, preto platí $k = k_1 + k_2 + ... + k_n$.

Príklad.
Tri modré kocky a 2 červené kocky ukladáme do radu. Zrejme záleží na poradí, pričom modrá kocka sa opakuje 4.krát a červená kocka sa opakuje 2-krát. Jedná sa o permutácie s opakovaním z dvoch prvkov/kategórií, kde prvý prvok sa opakuje 3x, druhý 2x.

1. $n$ počet všetkých kociek: 3 modré + 2 červené kocky
2. $k_1 = 3, k_2 = 2$
3. $n = 5 = k_1 + k_2 = 3 + 2$.
Skúste vypísať všetky permutácie, ktoré vyhovujú zadaniu. Poukladajte najskôr červené (dva) štvorčeky do zvislého radu, ktorý má 5 políčok.

Dostaneme 15 rôznych uložení 3 modrých a dvoch červených kociek.

Tvrdenie.
Počet permutácií s opakovaním z $n$, v ktorých sa jednotlivé prvky opakujú $k_1,k_2, \cdot \cdot \cdot ,k_n$-krát, je rovný číslu
$P'(k_1,k_2, \cdot \cdot \cdot ,k_n)=$ $\frac{ (k_1+k_2+ \cdot \cdot \cdot +k_n)!}{k_1!k_2! \cdot \cdot \cdot k_n!}$

Dôkaz.
Podobne ako v predchádzajúcom príklade určíme, koľkými spôsobmi by bolo možné prvky/štvorčeky zoradiť. Celkom je prvkov $k_1+k_2+...+k_n$, počet všetkých ich zoradení (permutácií) je preto 
$\small P(k_1+k_2+...+k_n)=( k_1+k_2+...+k_n)!$.
Pretože prvky nie sú všetky navzájom rôzne, budú sa niektoré v poradí opakovať:
     Prvý prvok sa bude opakovať $\small k_1!$.
     ...
    Pre každý prvok $i$-tý je počet opakovaní rovný $\small k_i!$. Výsledný počet poradí všetkých pasteliek je preto
$\small P'(k_1,k_2, \cdot \cdot \cdot ,k_n)=$ $\frac{ (k_1+k_2+ \cdot \cdot \cdot +k_n)!}{k_1!k_2! \cdot \cdot \cdot k_n!}$