Permutace

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

Permutace $\ n$ prvků je skupina všech $\ n$ prvků, které jsou uspořádány v jakémkoliv možném pořadí, tzn. výběr prvků závisí na pořadí. Rozlišujeme permutace bez opakování a s opakováním.

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

Obsah

1 Permutace bez opakování
- 1.1 Příklad
2 Permutace s opakováním
- 2.1 Příklad
3 Zápis
- 3.1 Příklad zápisu
4 Samodružný prvek
5 Inverzní permutace
6 Skládání permutací
- 6.1 Vlastnosti
- 6.2 Řád permutace
7 Příklad
8 Poznámky
9 Literatura
10 Související články

Permutace bez opakování

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 $\ n!$ označuje faktoriál.

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

Příklad

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

Permutace těchto prvků představují skupiny $a b c$ , $a c b$ , $b a c$ , $b c a$ , $c a b$ , $c b a$ . 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 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 $\ k$ skupin, které mají postupně $\ n_1,n_2,...,n_k$ stejných prvků. Musí přitom platit - $n = \sum_{i=1}^{k} n_i$

Příklad

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

Permutacemi s opakováním získáme skupiny $a a b$ , $a b a$ , $b a a$ . Počet těchto skupin je tedy roven

$P_{2,1}(3) = \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 = \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)$

Tato permutace je sudá.

Samodružný prvek

Každý prvek $r \in M$ , pro který platí $π(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

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 $π - 1$

Složením permutace $π$ a k ní inverzní permutace $π - 1$ získáme identickou permutaci.

Skládání permutací

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í $π 1,π 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}$

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

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 \,\!$

Řá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í.
Permutace s operací

Literatura

RDNR. PAVEL ČERMÁK, MGR. PETRA ČERVINKOVÁ. Odmaturuj z matematiky. [s.l.] : Didaktis, 2003 (druhé opravené vydání). ISBN 80-86285-97-9. Kapitola 35.Kombinatorika. (česky)

Související články

Tento matematický článek je příliš stručný nebo neobsahuje důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte.

Citováno z „http://cs.wikipedia.org/wiki/Permutace“

Kategorie: Kombinatorika | Algebra

Skrytá kategorie: Matematické pahýly

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car

This site monitored by SitePinger.net