Permutace je variace n prvků z n. Jednoduše řečeno se jedná o každé uspořádání n prvkové množiny, ve kterém se každý prvek vyskytuje právě jednou. Počet všech různých permutací z n prvků lze vyjádřit jako:


P(n) = n!

Za předpokladu, že umožníme, aby se některé prvky vyskytly vícekrát – tj. hledáme všechny k-prvková uspořádání n prvků, ve kterých se jednotlivé prvky vykytují k_{1},\\; k_{2},\\; k_{3},\\; \\cdots,\\; k_{n} krát – tak hovoříme o k prvkové permutaci s opakováním (k = k_{1} + k_{2} + k_{3} + \\cdots + k_{n}). Počet všech permutací s opakováním vypočítáme dle následujícího vzorce:


P'(k_{1}, \\; k_{2}, \\; k_{2},\\; \\cdots,\\; k_{n})= {{k!} \\over {k_{1}! \\cdot k_{2}! \\cdot k_{3}! \\cdots k_{n}!}

Příklad

Vypište všechny permutace (bez opakování) prvků a,\\; b,\\; c.

Řešení


P = \\{[a,\\; b,\\; c],\\; [a,\\; c,\\; b],\\; [b,\\; a,\\; c],\\; [b,\\; c,\\; a],\\; [c,\\; a,\\; b],\\; [c,\\; b,\\; a]\\}

Příklad

Vypište všechny (čtyřčlenné) permutace s opakováním prvků a,\\; b ve kterých se oba prvky vyskytují právě dvakrát.

Řešení


P' = \\{[a,\\; a,\\; b,\\; b],\\; [a,\\; b,\\; a,\\; b],\\; [a,\\; b,\\; b,\\; a],\\; [b,\\; a,\\; b,\\; a],\\; [b,\\; b,\\; a,\\; a],\\; [b,\\; a,\\; a,\\; b]\\}

Příklad

Kolika způsoby lze rozsadit 5 studentů do 5 lavic?

Řešení

Jedná se o problém uspořádání (záleží na pořadí) 5 prvků. Použijeme proto vzorec na permutaci (bez opakování). Bez znalosti vzorce bychom postupovali úvahou, že prvního studenta můžeme postadit do libovolné lavice (5 možností), druhého již jen do čtyř lavic (v jedné lavici už sedí první student), třetího do tří, čtvrtého do dvou a na posledního studenta již zbývá poslední lavice. Celkový počet uspořádání je proto:


P(5) = 5! = 5\\cdot 4\\cdot 3 \\cdot 2\\cdot 1 = 120

Příklad

Kolik permutací s opakováním lze vytvořit z písmen slova KOLO?

Řešení

Jedná se o čtyřčlenné permutace tří prvků, ve kterých se jeden prvek vyskytuje dvakrát a dva jednou.

P'(2,\\; 1,\\; 1) = {4! \\over (2!\\cdot 1!\\cdot 1!)} = {{24} \\over {2}} = 12

Lze vytvořit 12 permutací.

Literatura

  • POLÁK, Josef. Přehled středoškolské matematiky. 8. vydání. Praha 4 : Prometheus, 2005. 608 s.







Doporučujeme