Permutace Pro kterékoliv dvě množiny A, B symbolem BA značíme mno- žinu všech zobrazení g : A B. Jsou-li dále A, B, C jakékoliv tři množiny a jsou-li g : A B a h : B C jakákoliv zobra- zení, pak je k nim definováno složené zobrazení h g : A C. Připomeňme, že toto zobrazení h g je pro všechna a A defi- nováno předpisem (h g)(a) = h(g(a)). Zejména tedy pro libovolnou množinu X symbolem XX zna- číme množinu všech zobrazení : X X. Pak pro libovolná dvě zobrazení , : X X je definováno složené zobrazení : X X a toto zobrazení náleží opět do množiny XX . Uvažujme dále pouze libovolné bijekce f : X X. Tako- vým bijekcím říkáme permutace množiny X. Množinu všech permutací množiny X značíme S(X). Je to podmnožina v mno- žině XX a je uzavřená vzhledem ke skládání zobrazení, neboť složením kterýchkoliv dvou bijekcí z S(X) vznikne opět bijekce množiny X na X, čili zase prvek množiny S(X). Budeme dále vyšetřovat pouze permutace konečných množin. Přitom budeme kvůli přehlednosti pracovat pouze s množinami tvaru X = {1, 2, . . . , n}, kde n je přirozené číslo. Pak místo S(X) budeme psát Sn. Permutace Sn budeme zapisovat ve tvaru = 1 2 . . . n i1 i2 . . . in , kde pro každé r {1, 2, . . . , n} je ir = (r). Všimněme si, že pak (i1, i2, . . . , in) je obecně libovolná uspořádaná n-tice vzá- jemně různých prvků množiny {1, 2, . . . , n}, takže jde vlastně o prvky 1, 2, . . . , n zapsané v nějakém obecném pořadí. To zna- mená, že permutace Sn tímto způsobem vzájemně jedno- značně odpovídají permutacím (i1, i2, . . . , in) prvků 1, 2, . . . , n tak, jak je známe z kombinatoriky. Odtud plyne, že existuje 1 celkem n! permutací množiny {1, 2, . . . , n}. Kvůli odlišení ale budeme nyní uspořádaným n-ticím (i1, i2, . . . , in) vzájemně růz- ných prvků množiny {1, 2, . . . , n} říkat pořadí prvků 1, 2, . . . , n. Prvek r {1, 2, . . . , n} se nazývá samodružným prvkem permutace Sn, jestliže (r) = r. Nechť > 1 je přirozené číslo a nechť Sn je permutace. Pak tato permutace se nazývá cyklus délky , existují-li vzá- jemně různé prvky j1, j2, . . . , j {1, 2, . . . , n} takové, že platí (j1) = j2, (j2) = j3, . . . , (j -1) = j , (j ) = j1 a (r) = r pro všechna r {1, 2, . . . , n} - {j1, j2, . . . , j }. Takovou permu- taci pak zapisujeme jednodušeji ve tvaru = j1 j2 . . . j . Dva cykly = j1 j2 . . . j a = k1 k2 . . . km z Sn se nazývají nezávislé, jestliže {j1, j2, . . . , j }{k1, k2, . . . , km} = . Řekneme, že cykly 1, 2, . . . , t jsou vzájemně nezávislé, jestliže jsou nezávislé cykly p, q pro všechna p, q {1, 2, . . . , t}, p = q. Je vidět, že nezávislé cykly spolu při skládání komutují. Místo skládání permutací se někdy mluví též o součinu per- mutací. Věta. Každou neidentickou permutaci Sn lze vyjád- řit ve tvaru součinu několika navzájem nezávislých cyklů. Toto vyjadření je jediné až na pořadí zmíněných cyklů. Důkaz. Existenci uvedeného vyjádření dokážeme indukcí vzhledem k počtu samodružných prvků permutace . Poněvadž je neidentická permutace, existuje i {1, 2, . . . , n} takové, že (i) = i. Uvažme prvky i, (i), ((i)), (((i))), . . . . Značme prvky této posloupnosti h (i) pro h = 0, 1, 2, . . . . Poně- vadž množina {1, 2, . . . , n} je konečná, existují čísla , splňu- jící < taková, že (i) = (i). Předpokládejme dále navíc, 2 že je nejmenší takové číslo, k němuž existuje číslo < s uvedenou vlastností. Ukážeme, že pak platí = 0. V opač- ném případě, tedy kdyby bylo > 0, mohli bychom totiž psát (i) = (-1 (i)) a zároveň (i) = (-1 (i)), přičemž podle definice čísla by platilo -1 (i) = -1 (i), což ale není možné vzhledem k tomu, že je permutace. Takže skutečně = 0, a tedy máme i = (i). Přitom platí > 1, poněvadž (i) = i. Kromě toho z minimality čísla plyne, že prvky h (i) pro h = 0, 1, . . . , - 1 jsou vzájemně různé. Takže permutace = i (i) . . . -1 (i) je cyklus délky . Uvažme nyní permutaci -1 . Všechny samodružné prvky permutace jsou také samodružnými prvky permutace -1 . Navíc také prvky h (i) pro h = 0, 1, . . . , - 1 jsou očividně samodružnými prvky permutace -1 . Má tedy permutace -1 více samodružných prvků než permutace . Je-li -1 identická permutace, pak = . V opačném případě lze per- mutaci -1 podle indukčního předpokladu rozložit na součin vzájemně nezávislých cyklů ve tvaru -1 = 1 t. Při- tom prvky vystupující v cyklech 1, . . . , t nejsou samodružnými prvky permutace -1 , takže jsou různé od prvků h (i) pro h = 0, 1, . . . , - 1 vystupujících v cyklu . Takže odtud do- stáváme = 1 t, přičemž cykly a 1, . . . , t jsou vzájemně nezávislé. Jednoznačnost takového rozkladu je zřejmá. Cyklus délky 2, to znamená cyklus tvaru = i j , kde i, j {1, 2, . . . , n}, i = j, se nazývá transpozice. Věta. Nechť n > 1. Pak každou permutaci Sn lze vyjá- dřit ve tvaru součinu několika transpozic. Důkaz. Identickou permutaci lze vyjádřit například ve tvaru 1 2 1 2 . Pokud jde o neidentické permutace, z předchozí 3 věty plyne, že uvedené tvrzení stačí dokázat pro cykly. Pro libo- volný cyklus = j1 j2 . . . j ovšem platí j1 j2 . . . j = j1 j j1 j -1 j1 j3 j1 j2 , což potvrzuje možnost rozložit každou neidentickou permutaci na součin transpozic. Nechť (i1, i2, . . . , in) je libovolné pořadí prvků 1, 2, . . . , n. Jsou-li s, t {1, 2, . . . , n} takové prvky, že s < t a is > it, pak říkáme, že prvky is, it tvoří inverzi v pořadí (i1, i2, . . . , in). Pro libovolnou permutaci = 1 2 . . . n i1 i2 . . . in z Sn definujeme její paritu () předpisem () = (-1) (i1,i2,...,in) , kde (i1, i2, . . . , in) je celkový počet všech inverzí v pořadí (i1, i2, . . . , in). Říkáme, že uvedená permutace je sudá, je-li () = 1, to znamemá obsahuje-li pořadí (i1, i2, . . . , in) sudý počet inverzí. Říkáme, že tato permutace je lichá, je-li () = -1, to znamemá obsahuje-li pořadí (i1, i2, . . . , in) lichý počet inverzí. V kontextu předchozí věty ovšem charakterizujeme sudé a liché permutace ještě jiným způsobem. Věta. Nechť n > 1. Pak permutace Sn je sudá, resp. lichá, právě když každé vyjádření ve tvaru součinu transpozic obsahuje sudý, resp. lichý počet transpozic. Důkaz. Tvrzení bude dokázáno, ověříme-li, že pro libovolné transpozice i1 j1 , i2 j2 , . . . , it jt z Sn platí i1 j1 i2 j2 it jt = (-1)t , 4 tedy že složením sudého, resp. lichého počtu transpozic vznikne sudá, resp. lichá permutace. Poněvadž identická permutace je sudá, bude k tomu účelu stačit následující úvaha. Nechť Sn je libovolná permutace a nechť i, j {1, 2, . . . , n} jsou libovolné prvky splňující i = j, takže i j je libovolná transpozice. Pak stačí ověřit, že i j = -(), tedy že složení permutace s transpozicí mění paritu permutace. Ověříme tuto rovnost nejprve v případě, že uvedená trans- pozice je tvaru k k + 1 pro nějaké k {1, 2, . . . , n - 1}. Je-li ovšem (i1, i2, . . . , in) pořadí příslušné permutaci , je jasné, že pak (i1, . . . , ik-1, ik+1, ik, ik+2, . . . , in) je pořadí příslušné permu- taci k k + 1 . V tomto pořadí se změnila pouze poloha dvou sousedních prvků, což znamená, že počet inverzí se zvýšil nebo snížil o 1. Změnila se tudíž parita permutace. Uvažujme nyní obecnou transpozici, tedy transpozici tvaru i j , kde i, j {1, 2, . . . , n} splňují například i < j. Stačí si ale uvědomit, že takovou transpozici lze vyjádřit ve tvaru i j = i i + 1 i + 1 i + 2 j - 2 j - 1 j - 1 j j - 2 j - 1 i + 1 i + 2 i i + 1 , kde na pravé straně se vyskytuje lichý počet transpozic výše uvedeného speciálního tvaru. Pak už jen stačí použít toho, co bylo ukázáno v předchozím odstavci. Důsledek. Pro libovolné permutace , , Sn platí ( ) = ()(), (-1 ) = (). Důkaz. První rovnost ihned plyne z předchozích dvou vět. Druhá rovnost plyne z první a z faktu, že -1 je identická, a tedy sudá permutace. Buď n přirozené číslo. Označme An množinu všech sudých permutací množiny {1, 2, . . . , n}. Předpokládejme dále, že n > 1, 5 a vezměme libovolnou lichou permutaci Sn - An. Pak podle předchozího důsledku je možno uvažovat zobrazení : An Sn - An definované pro každou sudou permutaci An předpisem () = . Toto zobrazení podle již zmíněného důsledku převádí vzájemně jednoznačně všechny sudé permutace na liché permutace. In- verzním zobrazením ke je totiž zobrazení : Sn - An An definované pro každou lichou permutaci Sn - An předpisem () = -1 , neboť pak je identita na An a je identita na Sn - An. Čili a jsou vzájemně inverzní bijekce mezi množinami An a Sn - An. To ukazuje, že sudých i lichých permutací množiny {1, 2, . . . , n} je stejný počet a že tento počet je roven číslu n! 2 . 6