permutacja

Permutacja to bijekcja f: X → X, czyli odwracalny przekształcenie, które każdemu elementowi X przypisuje dokładnie jeden element tego samego zbioru. Dla zbioru o n elementach permutacje tworzą grupę S_n, zwaną grupą symetryczną, zawierającą wszystkie możliwe przestawienia kolejności elementów.

W praktyce permutację często opisuje się za pomocą postaci jednoliniowej lub rozkładu na cykle. Każdą permutację można zapisać jako product rozłączonych cykli, na przykład (1 3 2)(4 5) przedstawia zamianę 1→3, 3→2, 2→1 oraz 4↔5. To rozkład na cykle pomaga analizować strukturę permutacji, a elementy pozostające w jednym cyklu tworzą razem jego orbitę.

Własności: porządek permutacji to najmniejsza dodatnia liczba m taka, że f^m = id; jest to największa wspólna wielokrotność długości cykli w rozkładzie. Parzystość permutacji (parzysta vs. nieparzysta) zależy od liczby transpozycji potrzebnych do jej zapisania oraz od znaku (determinantu w zastosowaniach algebr). Parzyste i nieparzyste permutacje tworzą podgrupy, a grupa A_n zawiera tylko permutacje parzyste.

Liczenie: liczba permutacji n różnych elementów to n!. Dla multisetów, z powtórzeniami o długościach n1, n2, ..., nk, liczba różnych permutacji wynosi n!/(n1! n2! ... nk!). Derangements to permutacje bez punktów stałych.

Zastosowania obejmują combinatorikę, algebrę, kryptografię, teorie względności symetrii i algorytmy generowania porządków.