permutace

Permutace je pojem z kombinatoriky, který popisuje přeuspořádání prvků dané množiny. Pokud jde o konečnou množinu s n různými prvky, každé uspořádání všech n prvků je permutací té množiny. Například u množiny {a, b, c} existuje 3! = 6 různých permutací.

Matematicky lze permutace chápat jako bijekce z množiny na sebe; soubor všech permutací na n prvcích tvoří soubor S_n, tedy symetrická grupa. Operací je složení funkcí a velikost této grupy je n!.

Každá permutace se dá vyjádřit rozkladem na disjunktní cykly a dá se ji také zapsat jako soubor transpozic. Z hlediska algebraické charakteristiky se permutace rozlišují podle parity: některé lze vyjádřit jako sudý počet transpozic, jiné jako lichý počet.

Permutace s opakováním: pokud prvky nemají být všechny odlišné, počet odlišných permutací se mění. Obecný vzorec pro multiset je n! děleno součinem zpevněných faktorů multiplicit jednotlivých prvků, tj. n!/(m1! m2! … mk!). Příklad BALLOON (7 prvků s dvojicí L a dvojicí O) dává 7!/(2!2!) = 1260 permutací.

Použití permutací zahrnuje řešení úloh na uspořádání, generování pořadí, analýzu struktur a algoritmické problémy v informatice, kryptografii a teorii grafů.