Permutace Připomeňme, že pro libovolnou množinu X jsme symbolem X označili množinu všech zobrazení / : I-yXa symbolem o jsme označili skládání zobrazení. Uvažujme dále pouze libovolné bi-jekce / : X —>• X. Takový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 takových bijekcí vznikne opět bijekce. Budeme dále vyšetřovat pouze permutace konečných množin a přitom budeme 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 a G Sn budeme zapisovat ve tvaru kde ir = cr(r) pro každé r G {1, 2,... , n}. Poznamenejme, že pak «2, • • •, 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 znamená, že permutace a G Sn tímto způsobem odpovídají permutacím «2, • • •, in) prvků 1, 2,..., n tak, jak byly zavedeny v kombinatorice. Odtud plyne, že existuje celkem n! takových permutací. Kvůli odlišení ale budeme nyní uspořádaným n-ticím «2, • • •, in) vzájemně různých prvků množiny {1,2,..., n} říkat pořadí prvků 1, 2,..., n. Prvek r G {1, 2,..., n} se nazývá samodružným prvkem permutace a G Sn, jestliže a(r) = r. Nechť i > 1 je přirozené číslo a nechť a G Sn. Pak permutace a se nazývá cyklus délky £, existují-li vzájemně různé prvky ji, j2, G {1, 2,..., n} takové, že platí cr(ji) = j2, 1 v(J2) = h, }n{&i, fc2,..., = 0. Řekneme, že cykly 01, 02,..., o* jsou vzájemně nezávislé, jestliže jsou nezávislé cykly ap, aq pro všechna p, g G {1, 2,..., t}, p ^ q. Je vidět, že nezávislé cykly spolu při skládání komutují. Věta. Každou neidentickou permutaci a G Sn lze vyjádřit ve tvaru součinu několika navzájem nezávislých cyklů. Toto vyjádř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 a. Poněvadž a je neidentická permutace, existuje i G {1, 2,..., n} takové, že a (i) ^ i. Uvažme prvky i, a (i), (T {a (i)), a (a (a (i))), .... Značme prvky této posloupnosti ah(i) pro h = 0,1, 2,... . Poněvadž množina {1,2,..., n} je konečná, existují x, X splňující x. < X taková, že a*(i) = cA(«). Předpokládejme navíc, že A je nejmenší možné číslo s takovou vlastností. Ukážeme, že pak platí x = 0. V opačném případě bychom totiž měli = cr(crír_1(i)) a zároveň a*(i) = a(ax~1(i)), přičemž cr^-1^) ^ crA_1(i), což není možné vzhledem k tomu, že a je permutace. Takže x = 0, a tedy máme i = cA(«). Přitom platí A > 1, poněvadž a (i) ^ i. Kromě toho z minimality A plyne, že prvky oh{i) pro h = 0,1,..., A — 1 jsou vzájemně různé. Takže permutace r = (i a[i) ... a^ii)) je cyklus délky A. Uvažme nyní permutaci r-1 o a. Všechny sa-modružné prvky permutace a jsou také samodružnými prvky 2 permutace T~loa a navíc také prvky ah(i) pro h = 0,1,..., A — 1 jsou samodružnými prvky permutace r-1 o a. Má tedy permutace r-1 o a více samodružných prvků než permutace a. Je-li r-1 o a identická permutace, pak a = r. V opačném případě lze permutaci r-1 o a podle indukčního předpokladu rozložit na součin vzájemně nezávislých cyklů ve tvaru r-1 o a = p\ o ■ ■ ■ o pt. Přitom prvky vystupující v cyklech pi,..., pt nejsou samodružnými prvky permutace r-1 o cr, takže jsou různé od prvků ah(i) pro h = 0,1,..., A — 1 vystupujících v cyklu r. Takže odtud dostáváme a = r o p1 o ■ ■ ■ o ptl přičemž cykly r a pi,..., pt jsou vzájemně nezávislé. Jednoznačnost takového rozkladu je zřejmá. Cyklus délky 2, to znamená cyklus tvaru a = (i j), kde i, j G {1, 2,..., n}, i ^ j, se nazývá transpozice. Věta. Nechť n > 1. Pak každou permutaci a E Sn lze vyjádřit ve tvaru součinu několika transpozic. Důkaz. Identickou permutaci lze vyjádřit například ve tvaru (l 2) o (l 2). Pokud jde o neidentické permutace, z předchozí věty plyne, že tvrzení stačí dokázat pro cykly. Pro libovolný cyklus a = (ji j2 ... je) ovšem platí (ji J2 ■■■ je) = (ji je) ° (ji je-i) ° ■ ■ ■ ° (ji js) ° (ji 32) ■ Nechť «2, • • •, in) Je libovolné pořadí prvků 1, 2,..., n. Jsou-li s, t G {1,2,..., n} takové prvky, že s < t a is > it, pak říkáme, že prvky is, it tvoří inverzi v pořadí «2, • • •, in)- Pro libovolnou permutaci *=(1 2 - n) \ll %2 ■■■ %n) z Sn definujeme její paritu předpisem p(a) = (_i)3(*i,*2,...^)5 kde %(iui2j...,i„) je celkový počet všech inverzí v pořadí «2, • • •, in)- 3 Říkáme, že uvedená permutace a je sudá, je-li p{o) = 1, to znamemá obsahuje-li pořadí («1,«25 ■ ■ ■ 5«n) sudý počet inverzí. Říkáme, že tato permutace a je lichá, je-li p(cr) = —1, to znamemá obsahuje-li pořadí (ii,Í2, • • • ,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. Permutace a G Sn je sudá, resp. lichá, právě když každé vyjádření a 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 («i ji), (i2 j2), • • •, {h jt) z Sn platí p{{ň ji) ° («2 J2) 0 ■ ■ ■ 0 (it jt)) = (—1)*, 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ť a G Sn je libovolná permutace a nechť i, j G {1, 2,..., n} jsou libovolné prvky splňující i ^ j, takže (i j) je libovolná transpozice. Pak stačí ověřit, že p[a o (i j')) = —p(a), tedy že složení permutace s transpozicí mění paritu permutace. Ověříme tuto rovnost nejprve v případě, že uvedená transpozice je tvaru (k k + l) pro nějaké k G {1, 2,..., n — 1}. Je-li ovšem «2, • • •, in) pořadí příslušné permutaci cr, je jasné, že pak ..., ifc-i, ik+i, ik, ik+2, ■ ■ ■, in) je pořadí příslušné permutaci cro (k k + l). 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 G {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 + l)o(i + l i+ 2) o... o (j-2 j-1) o j) o (j - 2 j - l) o • • • o (i + 1 i + 2) o (i i + l) , 4 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 cr, r, p G Sn platí p{a o r) = p(cr)-p(r), p(p~l) = p(p). Důkaz. První rovnost ihned plyne z předchozích dvou vět. Druhá rovnost plyne z první a z faktu, ze po p~l 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}. Vezměme dále libovolnou lichou permutaci ů G Sn — An. Pak podle předchozího důsledku je možno uvažovat zobrazení 7 : An —y Sn — An definované pro každou sudou permutaci a G An předpisem 7(cr) = G o Toto zobrazení podle již zmíněného důsledku převádí vzájemně jednoznačně všechny sudé permutace na liché permutace. Skutečně inverzním zobrazením by bylo zobrazení '■ £>n — An \ An definované pro každou lichou permutaci r G Sn — An předpisem S(t) = toů~\ neboť pak S o 7 je identita na An a 7 o S je identita na 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 y. 5