Permutace

Permutace je speciálním případem variace, kdy máme množinu o velikosti n a chceme zjistit počet všech různých n-tic.

Vzorec

Zopakujeme si samotné variace. Mějme množinu číslic {1, 2, 3, 4, 5}, kolik trojciferných čísel z nich dokážeme sestavit, pokud se žádná číslice nesmí opakovat? To je typický příklad na variace, který lze vyřešit známým vzorcem

$$V(k,n)=\frac{n!}{(n-k)!}=\frac{5!}{(5-3)!}=60.$$

Kolik bychom dokázali poskládat pěticiferných čísel?

$$V(k,n)=\frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120.$$

Můžeme si všimnout, že pokud máme množinu o pěti prvcích a hledáme počet všech různých pětic, tak je výsledek rovný 5!. To můžeme zobecnit a říci, že pokud máme množinu o n prvcích, tak existuje celkem n! různých n-tic. Tím se dostáváme k pojmu permutace.

Co je to permutace

Pokud máme množinu M o velikosti n, pak permutace je libovolná n-tice složená z prvků z množiny M, přičemž žádný prvek se nesmí opakovat. Příklad: pokud máme množinu M = {a, b, c, d}, pak permutace je například [a, b, d, c] nebo [d, b, a, c]. Počet všech různých permutací je roven

$$P(n)=V(n,n)=n!$$

Řešené příklady

1. Máte celkem šest knih a chcete je uložit na poličku v nějakém pořadí. Kolik celkem různých pořadí existuje? Máme šest knih, permutujeme vždy všechny knihy, takže výsledek je roven P(6) = 6! = 720.

2. K vašim 6 českým knihám z minulého příkladu přibyly 4 knihy psané latinou. Kolik existuje různých způsobů jak uložit těchto 10 knih na poličku, pokud chcete mít všechny české u sebe a všechny latinské knihy u sebe?

   Jaké máme možnosti, jak knihy uložit? Můžeme nejdříve uložit šest českých knih a poté čtyři latinské nebo naopak — nejdříve čtyři latinské a pak šest českých. Přitom platí, že existuje 6! způsobů, jak uložit české knihy a 4! způsobů, jak uložit latinské knihy. Použijeme kombinatorické pravidlo součinu a tyto výsledky vynásobíme: 6! · 4! = 17 280. Protože existují dvě možnosti, jak knihy uložit (české, pak latinské a naopak), tak ještě toto číslo vynásobíme dvěma. Celkový výsledek je 17 280 · 2 = 34 560.

Zdroje a další čtení

• Kombinatorika na cuni.cz
• Bělohlávek, Vychodil: Diskrétní matematika [PDF]