Permutace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Permutace množiny, která obsahuje  \scriptstyle n prvků, je jedno z možných uspořádání těchto prvků, přičemž výsledná uspořádaná n-tice má stejný počet prvků jako původní množina. Někdy se také uvažují tzv. permutace s opakováním, což zahrnuje i takové uspořádní prvků, ve kterém se některé prvky vyskytují vícekrát.

Obecněji je permutace bez opakování chápána jako bijektivní zobrazení z množiny  \scriptstyle A na množinu  \scriptstyle A.

Permutace bez opakování[editovat | editovat zdroj]

Pokud se prvky ve výběru nemohou opakovat, pak počet všech možných výběrů je určen vztahem

 \ P(n) = n!,

kde  \scriptstyle n! označuje faktoriál, kde n je z oboru přirozených čísel včetně čísla 0.

Pokud se hovoří o permutacích prvků, jsou tím obvykle myšleny permutace bez opakování.

Příklad[editovat | editovat zdroj]

Mějme skupinu tří různých prvků a,b,c.

Permutace těchto prvků představují skupiny abc, acb, bac, bca, cab, cba. Jejich počet je tedy

 \ P(3) = 3! = 6

Permutace s opakováním[editovat | editovat zdroj]

Pokud se prvky ve výběru mohou opakovat, pak počet permutací s opakováním je určen jako

P_{n_1,n_2,...,n_k}(n) = \frac{n!}{{n_1!}\cdot{n_2!}\cdot...\cdot{n_k!}},

přičemž mezi vybranými prvky je  \scriptstyle k skupin, které mají postupně  \scriptstyle n_1,n_2,...,n_k stejných prvků. Musí přitom platit:

n = \sum_{i=1}^{k} n_i


Příklad[editovat | editovat zdroj]

Mějme skupinu tří prvků a,a,b. Skupina je tedy složena ze dvou skupin (tedy  \scriptstyle k=2), přičemž první skupina má dva prvky  \scriptstyle a, tzn.  \scriptstyle n_1 = 2, a druhá skupina obsahuje jeden prvek  \scriptstyle b, tzn.  \scriptstyle n_2 = 1.

Permutacemi s opakováním získáme skupiny aab, aba, baa. Počet těchto skupin je tedy roven

P_{2,1}(3) = \frac{3!}{{2!}\cdot{1!}} = 3

Zápis[editovat | editovat zdroj]

Permutace lze zapsat tabulkou, kde v horním řádku je vstupní hodnota funkce a v dolním její výsledná hodnota. Nebo se zapisuje jako spojení cyklů nebo transpozic.

Permutace je lichá, pokud lze vyjádřit spojením lichého počtu cyklů délky 2. Permutace je sudá, pokud lze vyjádřit spojením sudého počtu cyklů délky 2.

Příklad zápisu[editovat | editovat zdroj]

Pomocí tabulky lze permutaci množiny \{1,2,3,4,5,6\} zapsat jako

\pi = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 1 & 5 & 2 & 4 &6\end{pmatrix}

Pomocí cyklů a transpozic lze předchozí permutaci zapsat jako

\pi = (1,3,5,4,2) = (1,3) \circ (3,5,4,2) = (1,3) \circ (3,5) \circ (5,4) \circ (4,2)

Tento rozklad je špatný. Správně je to (1,3) o (1,5) o (1,4) o (1,2). Jenom tak potom platí skládání permutací (zleva doprava) a opětně vrátí výsledek (1,3,5,4,2).

Tato permutace je sudá.

Samodružný prvek[editovat | editovat zdroj]

Každý prvek r \in M, pro který platí \pi(r)=r, se nazývá samodružným prvkem. V opačném případě se jedná o prvek nesamodružný.

Jestliže každý prvek permutace je samodružný, pak hovoříme o identické (jednotkové) permutaci. Příkladem takové permutace je

\pi = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 &6\end{pmatrix}

Inverzní permutace[editovat | editovat zdroj]

K permutaci

\pi = \begin{pmatrix}a_1 & a_2 & ... & a_n \\ b_1 & b_2 & ... & b_n\end{pmatrix}

je možné vytvořit inverzní permutaci

\pi^{-1} = \begin{pmatrix}b_1 & b_2 & ... & b_n \\ a_1 & a_2 & ... & a_n\end{pmatrix}

Inverzní permutaci značíme \scriptstyle \pi^{-1}

Složením permutace \scriptstyle \pi a k ní inverzní permutace \scriptstyle \pi^{-1} získáme identickou permutaci.

Skládání permutací[editovat | editovat zdroj]

Mějme na množině M dvě permutace

\pi_1 = \begin{pmatrix}a_1 & a_2 & ... & a_n \\ b_1 & b_2 & ... & b_n\end{pmatrix}
\pi_2 = \begin{pmatrix}b_1 & b_2 & ... & b_n \\ c_1 & c_2 & ... & c_n\end{pmatrix}

Složením permutací \pi_1, \pi_2 (hovoříme také o součinu permutací) je permutace

\pi = \begin{pmatrix}a_1 & a_2 & ... & a_n \\ c_1 & c_2 & ... & c_n\end{pmatrix}

(pozor, toto je skládání zleva doprava, někdy se používá opačné)

Součin permutací zkráceně zapíšeme \pi = \pi_1 \circ \pi_2

Násobení permutací není v obecném případě komutativní, tzn. \pi_1 \circ \pi_2 \neq \pi_2 \circ \pi_1.

Příklad[editovat | editovat zdroj]

\pi_1 = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 3 & 1 & 5 & 2\end{pmatrix}
\pi_2 = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 2 & 4 & 1 & 3 & 6\end{pmatrix}

Za použití výše uvedené metody způsobu zápisu permutace vypadají následovně

\pi_1 = (1, 6, 2, 4)
\pi_2 = (1, 5, 3, 4)

Složením permutací \pi_1 a \pi_2 rozumíme permutaci \pi_2 \circ \pi_1 = (1, 5, 3, 4) \circ (1, 6, 2, 4) Permutace skládáme jako funkce, tedy zprava doleva. Nejprve se podíváme na první prvek permutace \pi_1 . V ní číslo 1 jde na číslo 6. Pak se podíváme kam jde 6 v \pi_2. Permutace \pi_2 o čísle 6 nic neříká, tedy píšeme

(1 6

Teď se podívám kam jde 6 v \pi_1. Na 2. Druhá permutace opět o 2 nehovoří. Tedy pokračujeme v zápisu

(1 6 2

Číslo 2 jde \pi_1 na 4, ale číslo 4 jde v \pi_2 na 1 a tento provek už máme jako začátek našeho cyklu. Tedy zatím počítáme správně. Pokud by nám vyšlo nějaké číslo, které není na začátku cyklu, pak je někde chyba. Tedy uzavíráme cyklus.

(1 6 2)

Teď se podíváme na číslo do permutace vpravo, které jsme ještě nepoužili (není napsáno v již uzavřeném cyklu). Takovým číslem je 4. Číslo 4 jde v \pi_1 na 1 a ta jde v \pi_2 na 5. To zapíšeme

(1 6 2)(4 5

a provedeme tento postup pro zbylá čísla (zde chybí už jenom číslo 5). Tedy výsledek je

\pi_2 \circ \pi_1 = (1, 5, 3, 4) \circ (1, 6, 2, 4) = (1, 6, 2)(4, 5, 3)

Pozn.: Výsledek lze interpretovat také třeba jako (216)(534), neboť (216) = (162) = (621).

Vlastnosti[editovat | editovat zdroj]

Máme-li na dané množině M permutace \scriptstyle \pi, \pi_1, \pi_2, \pi_3 \,\! a identickou permutaci \scriptstyle I \,\!, pak platí vztahy

\pi_1 \circ ( \pi_2 \circ \pi_3) = ( \pi_1 \circ \pi_2) \circ \pi_3 \,\!
\pi \circ I = I \circ \pi = \pi \,\!
\pi^{-1} \circ \pi = \pi \circ \pi^{-1} = I \,\!

To jsou axiomy grupy splněné obecně pro každou množinu permutací P(n), kde grupovým násobením je součin dvou permutací. Tedy množina permutací P(n) společně se skládáním permutací tvoří grupu.

Řád permutace[editovat | editovat zdroj]

Máme-li permutaci  \scriptstyle \pi,  \scriptstyle \pi^k značí permutaci vzniklou k-násobným složením permutace  \scriptstyle \pi, tj.  \scriptstyle \pi^1 = \pi, \scriptstyle \pi^k = \pi \circ \pi^{k-1}. Řád permutace je nejmenší přirozené číslo k takové, pro které platí  \scriptstyle \pi^k = I, tj. po k složeních vznikne identická permutace.

Příklad[editovat | editovat zdroj]

Zobrazení  \scriptstyle f(a)=a+1 na celých číslech je permutace. Máme-li nyní permutaci  \scriptstyle g(a) = a-3 definovanou na celých číslech. Pak :f \circ g(a) = f(g(a)) = f(a - 3) = a - 2.

Poznámky[editovat | editovat zdroj]

Literatura[editovat | editovat zdroj]

  • ČERMÁK, Pavel; ČERVINKOVÁ, Petra. Odmaturuj z matematiky. [s.l.] : Didaktis, 2003 (druhé opravené vydání). ISBN 80-86285-97-9. Kapitola 35. Kombinatorika.  

Související články[editovat | editovat zdroj]