Permutace

Šablona:Upravit Šablona:Neověřeno Permutace n-prvkové množiny je uspořádaná n-tice obsahující každý prvek právě jednou, takže jednoznačně určuje jedno z možných uspořádání těchto prvků. Odtud (řídce užívané) české synonymum pro permutaci pořadí. Ekvivalentní definice je, že se jedná o n-prvkovou variaci z n prvků.

V kombinatorice se také uvažují permutace s opakováním, zahrnující i taková uspořádání prvků, ve kterém se některé prvky vyskytují vícekrát.

Obecně je permutace (bez opakování) chápána jako bijektivní zobrazení množiny na sebe.

Permutace bez opakování

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

$P(n)=n!,$

kde n! (čteme "en faktoriál") označuje hodnotu posloupnosti zvané faktoriál čísla n.

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

Příklad

Mějme tři různé prvky $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

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

$P^{\prime }(k_1,k_2,...,k_n)=\frac{(k_1+k_2+...+k_n)!}{k_1!\cdot k_2!\cdot ...\cdot k_n!}$,

kde se jednotlivé prvky opakují $k_1,k_2,...,k_n-$krát.

Příklad

Mějme skupinu tří písmen $a,a,b$. Trojice je tedy složena ze dvou prvků (tedy $n=2$), přičemž první prvek $a$ se opakuje dvakrát, tzn. $k_1=2$, a druhý prvek $b$ se opakuje jednou, tzn. $k_2=1$.

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

$P^{\prime }(2,1)=\frac{3!}{2!\cdot 1!}=3$

Zápis

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

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

$\pi =\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 3& 1& 5& 2& 4& 6\end{array}\right)$

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)$

Tato permutace je sudá.

Samodružný prvek

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

Naříklad permutace

$\pi =\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 1& 3& 2& 5& 4& 6\end{array}\right)$

má samodružné prvky 1 a 6.

Jestliže každý prvek permutace je samodružný, pak jde o identickou (jednotkovou) permutaci.

Počet všech permutací n-prvkové množiny bez samodružných prvků se nazývá subfaktoriál a značí "!n".

Inverzní permutace

K permutaci

$\pi =\left(\begin{array}{cccc}{a}_1& a_2& ...& a_n\\ b_1& b_2& ...& b_n\end{array}\right)$

je možné vytvořit inverzní permutaci

${\pi }^{-1}=\left(\begin{array}{cccc}{b}_1& b_2& ...& b_n\\ a_1& a_2& ...& a_n\end{array}\right)$

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

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

Skládání permutací

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

${\pi }_1=\left(\begin{array}{cccc}{a}_1& a_2& ...& a_n\\ b_1& b_2& ...& b_n\end{array}\right)$

${\pi }_2=\left(\begin{array}{cccc}{b}_1& b_2& ...& b_n\\ c_1& c_2& ...& c_n\end{array}\right)$

Složením permutací ${\pi }_1,{\pi }_2$ (hovoříme také o součinu permutací) je permutace

$\pi =\left(\begin{array}{cccc}{a}_1& a_2& ...& a_n\\ c_1& c_2& ...& c_n\end{array}\right)$

(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\ne {\pi }_2\circ {\pi }_1$.

Příklad

${\pi }_1=\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 6& 4& 3& 1& 5& 2\end{array}\right)$

${\pi }_2=\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 5& 2& 4& 1& 3& 6\end{array}\right)$

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áme, 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 prvek 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

Máme-li na dané množině $M$ permutace $\pi ,{\pi }_1,{\pi }_2,{\pi }_3$ a identickou permutaci $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

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

Příklad

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

Poznámky

• Determinant je definován pomocí permutací.

Literatura

• Šablona:Citace monografie

Související články

• Variace
• Kombinace
• Znaménko permutace
• Algoritmus Permutace

Externí odkazy

• Šablona:Commonscat
• Šablona:Otto