Kombinatorika: Permutácie s opakovaním

Kombinatorika

Variácie s opakovaním

Permutácie s opakovaním

Definícia.
Permutácia s opakovaním z

$n$ prvkov je usporiadaná

$k$ -tica zostavená z týchto

$n$ prvkov taká, že každý prvok 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 stĺpcov. Zrejme záleží na poradí, pričom modrá kocka sa opakuje 3-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.

$n$ počet všetkých kociek: 3 modré + 2 červené kocky
$k_1 = 3, k_2 = 2$
$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 10 rôznych uložení 3 modrých a dvoch červených kociek.

Tvrdenie.
Počet permutácií s opakovaním z

$n$ prvkov, v ktorých sa jednotlivé prvky opakujú

$\small k_1,k_2, \cdot \cdot \cdot ,k_n$ -krát, je rovný číslu

$\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!}$

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

$\small 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ť