Permutace Jan Paseka Masarykova univerzita Brno Permutace ­ p.1/20 Abstrakt Permutace ­ p.2/20 Abstrakt V této kapitole se zaměříme na permutace konečných množin ­ Permutace ­ p.2/20 Abstrakt V této kapitole se zaměříme na permutace konečných množin ­ zavedeme pojmy cyklus, transpozice, parita, inverze, sudá a lichá permutace. Ukážeme bijekci mezi sudými a lichými permutacemi. Permutace ­ p.2/20 Obsah přednášky Permitace. Cyklus. Transpozice. Permutace ­ p.3/20 Obsah přednášky Permitace. Cyklus. Transpozice. Inverze. Parita. Sudá a lichá permutace. Permutace ­ p.3/20 Permutace Připomeňme, že pro libovolnou množinu X jsme symbolem XX označili množinu všech zobrazení f : X X a symbolem jsme označili skládání zobrazení. Permutace ­ p.4/20 Permutace Připomeňme, že pro libovolnou množinu X jsme symbolem XX označili množinu všech zobrazení f : X X a symbolem jsme označili skládání zobrazení. Uvažujme dále libovolné bijekce f : 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í. Permutace ­ p.4/20 Permutace Připomeňme, že pro libovolnou množinu X jsme symbolem XX označili množinu všech zobrazení f : X X a symbolem jsme označili skládání zobrazení. Uvažujme dále libovolné bijekce f : 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í. Permutace ­ p.4/20 Permutace konečných množin I 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 ­ p.5/20 Permutace konečných množin I 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). Permutace ­ p.5/20 Permutace konečných množin II = 1 2 . . . n i1 i2 . . . in P ermutace ­ p.6/20 Permutace konečných množin II = 1 2 . . . n i1 i2 . . . in 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í. Permutace ­ p.6/20 Permutace a kombinatorika Permutace Sn tedy vzájemně jednoznačně odpovídají permutacím (i1, i2, . . . , in) prvků 1, 2, . . . , n tak, jak byly zavedeny v kombinatorice. Permutace ­ p.7/20 Permutace a kombinatorika Permutace Sn tedy vzájemně jednoznačně odpovídají permutacím (i1, i2, . . . , in) prvků 1, 2, . . . , n tak, jak byly zavedeny v kombinatorice. Odtud plyne, že existuje celkem n! permutací množiny {1, 2, . . . , n}. Permutace ­ p.7/20 Permutace a kombinatorika Permutace Sn tedy vzájemně jednoznačně odpovídají permutacím (i1, i2, . . . , in) prvků 1, 2, . . . , n tak, jak byly zavedeny v kombinatorice. Odtud plyne, že existuje celkem n! permutací množiny {1, 2, . . . , n}. Kvůli odlišení budeme uspořádaným n-ticím (i1, i2, . . . , in) vzájemně různých prvků množiny {1, 2, . . . , n} říkat pořadí prvků 1, 2, . . . , n. Permutace ­ p.7/20 Samodružný prvek permutace Prvek r {1, 2, . . . , n} se nazývá samodružným prvkem (pevným bodem) permutace Sn, jestliže (r) = r. Permutace ­ p.8/20 Samodružný prvek permutace Prvek r {1, 2, . . . , n} se nazývá samodružným prvkem (pevným bodem) permutace Sn, jestliže (r) = r. Připomeňme si, že pomocí principu inkluze a exkluze lze počet permutací, které nemají žádný pevný bod vyjádřit výrazem Permutace ­ p.8/20 Samodružný prvek permutace Prvek r {1, 2, . . . , n} se nazývá samodružným prvkem (pevným bodem) permutace Sn, jestliže (r) = r. Připomeňme si, že pomocí principu inkluze a exkluze lze počet permutací, které nemají žádný pevný bod vyjádřit výrazem n! n =0 (-1) ! n! e . Permutace ­ p.8/20 Cykly I Necht' > 1 je přirozené číslo a necht' Sn je permutace. Permutace ­ p.9/20 Cykly I Necht' > 1 je přirozené číslo a necht' Sn je permutace. 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 r {1, 2, . . . , n} - {j1, j2, . . . , j}. Permutace ­ p.9/20 Cykly II Cyklus pak zapisujeme jednodušeji ve tvaru = j 1 j2 . . . j . Permutace ­ p.10/20 Cykly II Cyklus pak zapisujeme jednodušeji ve tvaru = j 1 j2 . . . j . Dva cykly = j 1 j2 . . . j a = k 1 k2 . . . km z Sn se nazývají nezávislé, jestliže {j1, j2, . . . , j} {k1, k2, . . . , km} = . Permutace ­ p.10/20 Cykly II Cyklus pak zapisujeme jednodušeji ve tvaru = j 1 j2 . . . j . Dva cykly = j 1 j2 . . . j a = k 1 k2 . . . km z Sn se nazývají nezávislé, jestliže {j1, j2, . . . , j} {k1, k2, . . . , km} = . 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. Permutace ­ p.10/20 Cykly III Nezávislé cykly , spolu při skládání komutují tj. platí = . Permutace ­ p.11/20 Cykly III Nezávislé cykly , spolu při skládání komutují tj. platí = . 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ů. Permutace ­ p.11/20 Transpozice Cyklus délky 2, to znamená cyklus tvaru = i j , kde i, j {1, 2, . . . , n}, i = j, se nazývá transpozice. Permutace ­ p.12/20 Transpozice Cyklus délky 2, to znamená cyklus tvaru = i j , kde i, j {1, 2, . . . , n}, i = j, se nazývá transpozice. Věta. Necht' n > 1. Pak každou permutaci Sn lze vyjádřit ve tvaru součinu několika transpozic. Permutace ­ p.12/20 Inverze Necht' (i1, i2, . . . , in) je libovolné pořadí prvků 1, 2, . . . , n. Permutace ­ p.13/20 Inverze Necht' (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). Permutace ­ p.13/20 Inverze Necht' (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). Permutace ­ p.13/20 Parita Pro libovolnou permutaci = 1 2 . . . n i1 i2 . . . in z Sn definujeme její paritu () předpisem Permutace ­ p.14/20 Parita Pro libovolnou permutaci = 1 2 . . . n i1 i2 . . . in z Sn definujeme její paritu () předpisem () = (-1)In(i1,i2,...,in) , Permutace ­ p.14/20 Parita Pro libovolnou permutaci = 1 2 . . . n i1 i2 . . . in z Sn definujeme její paritu () předpisem () = (-1)In(i1,i2,...,in) , kde In(i1, i2, . . . , in) je celkový počet všech inverzí v pořadí (i1, i2, . . . , in). Permutace ­ p.14/20 Sudá a lichá permutace Ř íkáme, že permutace je sudá, je-li () = 1, to znamená obsahuje-li pořadí (i1, i2, . . . , in) sudý počet inverzí. Permutace ­ p.15/20 Sudá a lichá permutace Ř íkáme, že permutace je sudá, je-li () = 1, to znamená obsahuje-li pořadí (i1, i2, . . . , in) sudý počet inverzí. Ř íkáme, že permutace je lichá, je-li () = -1, to znamená obsahuje-li pořadí (i1, i2, . . . , in) lichý počet inverzí. Permutace ­ p.15/20 Sudá a lichá permutace Ř íkáme, že permutace je sudá, je-li () = 1, to znamená obsahuje-li pořadí (i1, i2, . . . , in) sudý počet inverzí. Ř íkáme, že permutace je lichá, je-li () = -1, to znamená obsahuje-li pořadí (i1, i2, . . . , in) lichý počet inverzí. Věta. 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 trans- pozic. Permutace ­ p.15/20 Parita součinu permutací Důsledek. Pro libovolné permutace , , Sn platí ( ) = ()(), (-1 ) = (). Permutace ­ p.16/20 Příklady inverzí I = 1 2 3 1 2 3 . nemá žádné inverze, je tedy sudá permutace a () = 1. Permutace ­ p.17/20 Příklady inverzí I = 1 2 3 1 2 3 . nemá žádné inverze, je tedy sudá permutace a () = 1. = 1 2 3 1 3 2 . má jednu inverzi (čísla 3 a 2 tvoří inverzi), je tedy lichá permutace a () = -1. Permutace ­ p.17/20 Příklady inverzí II = 1 2 3 2 3 1 . má jednu inverzi (čísla 2 a 1 tvoří inverzi, 3 a 1 tvoří inverzi), je tedy sudá permutace a () = 1. Permutace ­ p.18/20 Příklady inverzí II = 1 2 3 2 3 1 . má jednu inverzi (čísla 2 a 1 tvoří inverzi, 3 a 1 tvoří inverzi), je tedy sudá permutace a () = 1. = 1 2 3 3 1 2 . má dvě inverzie (čísla 3 a 1 tvoří inverzi, čísla 3 a 2 tvoří inverzi), je tedy sudá permutace a () = 1. Permutace ­ p.18/20 Množina sudých permutací Bud' 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 Sn - An. Permutace ­ p.19/20 Množina sudých permutací Bud' 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 Sn - An. Je možno uvažovat zobrazení : An Sn - An definované pro každou sudou permutaci An předpisem () = . Permutace ­ p.19/20 Zobrazení Zobrazení převádí vzájemně jednoznačně všechny sudé permutace na liché permutace. Permutace ­ p.20/20 Zobrazení Zobrazení převádí vzájemně jednoznačně všechny sudé permutace na liché permutace. Inverzním zobrazením k je zobrazení : Sn - An An definované pro každou lichou permutaci Sn - An předpisem () = -1 . Permutace ­ p.20/20 Zobrazení Zobrazení převádí vzájemně jednoznačně všechny sudé permutace na liché permutace. Inverzním zobrazením k je zobrazení : Sn - An An definované pro každou lichou permutaci Sn - An předpisem () = -1 . Tedy je identita na An a je identita na Sn - An, |An| = |Sn - An| = n! 2 . Permutace ­ p.20/20