✖

Permutace

Kapitoly: Kombinatorika, Variace, Permutace, Kombinace, Variace s opakováním, Kombinace s opakováním, Kolik existuje různých PINů, Kalkulačka: Kombinační číslo

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 velikost 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, permutuje 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ým 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 sečteme: 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í