6. Permutace Flashcards
definice permutace
6.1. Definice. Nechť M je konečná množina. Permutací množiny M nazveme
každé vzájemně jednoznačné zobrazení (bijekci) množiny M na množinu M.
slozeni permutací
Permutace množiny M skládáme jako zobrazení; složením permutací P a Q
(v tomto pořadí) rozumíme složené zobrazení QP , které každému číslu i ∈ M
přiřadí číslo Q(P (i)). Složení dvou permutací množiny M je opět nějaká permutace
množiny M , neboť složení dvou bijekcí je opět bijekce. Jsou-li např.
P=
1 2 3 4 5
2 5 4 3 1 a Q=
1 2 3 4 5
1 3 5 2 4
permutace množiny M= {1, 2, 3, 4, 5}, je
QP=
1 2 3 4 5
3 4 2 5 1 a P Q=
1 2 3 4 5
2 4 1 5 3.
Skládání permutací tedy není komutativní. Přesto se může stát, že pro nějaké
permutace P, Q množiny M platí rovnost P Q= QP ; v tomto případě říkáme, že
permutace P, Q jsou záměnné, resp. komutující.
veta o grupach permutaci + dukaz
6.2. Věta. Množina všech permutací n-prvkové množiny M spolu s operací sklá-
dání tvoří grupu. Tato grupa má n! prvků.
Důkaz. Skládání permutací je podle předešlého binární operací na množině všech
permutací množiny M . Tato operace je asociativní, neboť již skládání zobrazení
je asociativní. Identické zobrazení 1M množiny M na množinu M je tzv. identická
permutace, která je jednotkovým prvkem při skládání permutací množiny M . Ke
každé permutaci
P=
1 2 . . . n
a1 a2 . . . an
množiny M existuje permutace P−1 taková, že P·P−1 = P−1
P−1 se nazývá inverzní permutace k permutaci P ; zřejmě je
·P = 1M . Permutace
P−1
=
a1 a2 . . . an
1 2 . . . n
.
Množina všech permutací množiny M spolu s operací skládání permutací je tedy
grupa. Indukcí snadno dokážeme, že n-prvková množina má právě n! různých per-
mutací.
definice symetricka grupa
6.3. Definice. Grupa všech permutací n-prvkové množiny se nazývá symetrická
grupa stupně n. Značí se obvykle Sn.
definice inverzni permutace a znamenko
6.4. Definice. Nechť P je permutace množiny M. Inverzí permutace P budeme
rozumět každou dvouprvkovou podmnožinu {i, j} množiny M , kde
i < j a P (i) > P (j).
Znaménko8 sgn P permutace P definujeme rovností
sgn P = (−1)in P
,
kde in P je počet všech inverzí permutace P . Permutace P se nazývá sudá, resp.
lichá, jestliže je sgn P = 1, resp. sgn P=−1.
Permutace je tedy sudá, resp. lichá, má-li sudý, resp. lichý počet inverzí. Iden-
tická permutace 1M nemá žádnou inverzi a je proto sudá.
