Permutace s opakováním

Poznámka k videu

Nyní k pojmu permutace s opakováním. V tomto případě nebude myšlenka tak snadná, jako v případě permutací bez opakování. Zkusíme si motivaci výpočtu představit na příkladu.

Představme si, že máme písmena abecedy, ze kterých chceme složit slova (nemusí mít význam). Máme například \(3\times A\), \(2\times B\), \(4\times N\). Kolik bude existovat takových slov? Tak nejprve budeme pro jednoduchost předpokládat, že jsou všechna písmena jsou různá. Pak tedy máme \(3+2+4=9\) prvků, které seřazujeme, což je \(9!\) možností. Pokud tedy máme obecně \(a_1\), \(a_2\), ..., \(a_n\) prvků a ty se mohou opakovat postupně \(k_1\), \(k_2\), ..., \(k_n\) krát, tak máme dohromady \(k_1+k_2+\dots+k_n\) prvků, které přeřazujeme, což je \((k_1+k_2+\dots+k_n)!\) možností.

To ale není vše, je nám jasné, že jsme nezohlednili to, že některé prvky jsou stejné, tedy navzájem zaměnitelné, takže máme více možností než je správně. Zpátky k našem příkladu s písmeny, máme \(3\times A\), tedy pokud zvolíme konkrétní permutaci prvků, tak pokud budu vyměňovat písmena \(A\) mezi sebou, budu mít stále stejný výsledek, tedy tyto možnosti chci sjednotit v jednu. Možností, jak přeřadit písmena \(A\) je v tomto případě \(3!\) a tolikrát více odpovědí máme, tedy tímto budeme muset možnosti vydělit. Podobně \(2!\) pro písmeno \(B\) a \(4!\) pro písmeno \(N\). Tedy dohromady máme:

\(\dfrac{9!}{3! \cdot 2! \cdot 4!}\)

výsledných možností.

Pokud se vrátíme k naším předchozím obecným možnostem, tak tam máme na prvek \(a_1\) dohromady \(k_1!\) možností přeřazení, pro další \(k_2!\) a tak dále až po \(k_n!\). Tedy vzorec pro výpočet pro permutace s opakováním \(a_1\), \(a_2\), ..., \(a_n\) prvků kde máme postupně pro tyto prvky \(k_1\), \(k_2\), ..., \(k_n\) možností pro opakování je:

\(P'(k_1, k_2, ..., k_n)=\dfrac{(k_1+k_2+\dots +k_n)!}{k_1! \cdot k_2! \cdot \dots \cdot k_n!}\)

Tento vzoreček působí na první pohled celkem komplikovaně, proto je dobré chápat jeho tvorbu, protože je poté pravděpodobnější, že výpočet v dané slovní úloze zvládneme použít a hlavně modifikovat podle potřeby.