Permutacja zbioru skończonego \( X \) to bijekcja z \( X \) w \( X \).
Zbiór permutacji zbioru \( \mathbb{Z}_n \) oznaczamy przez \( S_n \), a permutacje bedziemy w tym kursie oznaczać małymi literami greckimi.
Przykład
Rozważ funkcję \( \alpha:\mathbb{Z}_7 \to \mathbb{Z}_7 \) zadaną przez poniższą tabelę:
\( \begin{array} {|c||c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \alpha(n) & 2 & 3 & 6 & 0 & 4 & 1 & 5 \\ \hline \end{array} \)
Funkcja \( \alpha \) jest bijekcją z \( \mathbb{Z}_7 \) w \( \mathbb{Z}_7 \), zatem jest permutacją i \( \alpha\in S_7 \).
Przykład
Dla permutacji \( \alpha,\beta\in S_5 \) zadanych przez poniższą tabelę:
\( \begin{array} {|c||c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 \\ \hline \alpha(n) & 4 & 2 & 3 & 0 & 1 \\ \hline \beta(n) & 2 & 3 & 1 & 4 & 0 \\ \hline \end{array} \)
ich złożenia podane są poniżej:
\( \begin{array} {|c||c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 \\ \hline \beta\alpha(n) & 0 & 1 & 4 & 2 & 3 \\ \hline \alpha\beta(n) & 3 & 0 & 2 & 1 & 4 \\ \hline \end{array} \)
Zauważ, że oba złożenia także są permutacjami \( \mathbb{Z}_5 \).
Ponieważ permutacje są bijekcjami, to natychmiast z Obserwacji 3.2 dostajemy:
Obserwacja 3.12
Dla dowolnych permutacji \( \alpha,\beta \) skończonego zbioru \( X \):
Następne spostrzeżenie jest natychmiastowym wnioskiem z Obserwacji 3.11.
Wniosek 3.13
Zbiór \( n \)-elementowy ma dokładnie \( n! \) permutacji, \( \vert S_n\vert=n! \).
Przykład
Oto wszystkie (\( 3!=6 \)) permutacje zbioru \( S_3 \):
\( \begin{array} {ccccccccccc} 0 & 1 & 2 & \qquad & 0 & 1 & 2 & \qquad & 0 & 1 & 2 \\ \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow \\ 0 & 1 & 2 & \qquad & 0 & 2 & 1 & \qquad & 1 & 0 & 2 \\ \\ 0 & 1 & 2 & \qquad & 0 & 1 & 2 & \qquad & 0 & 1 & 2 \\ \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow \\ 1 & 0 & 2 & \qquad & 2 & 0 & 1 & \qquad & 2 & 1 & 0 \end{array} \)
Permutację \( \alpha \) zbioru \( X={\{ {x_0,\ldots,x_{n-1}} \}\ } \) wygodnie jest identyfikować z krotką \( (\alpha(x_0),\ldots,\alpha(x_{n-1}))\in X^n \). Często też permutację interpretuje się jako uporządkowanie zbioru \( X \).
Przykład
Na ile sposobów można poukładać koło siebie na półce \( 7 \) książek?
Na dokładnie tyle, ile jest permutacji zbioru siedmio-elementowego, a więc \( 7!=5040 \).
Cykl zbioru \( n \)-elementowego \( X \) to taka permutacja zbioru \( X \), dla której \( {\{ {x,\alpha(x),\alpha^2(x),\ldots,\alpha^{n-1}(x)} \}\ }=X \), przy dowolnym \( x\in X \). Łatwo zauważyć, że jeśli dla pewnego \( x_0\in X \) mamy \( {\{ {x,\alpha(x),\alpha^2(x),\ldots,\alpha^{n-1}(x)} \}\ }=X \), to jest tak dla wszystkich \( x\in X \), czyli \( \alpha \) jest cyklem na \( X \). Cykl \( \alpha \) zbioru \( X \) zapisujemy jako \( (x,\alpha(x),\ldots,\alpha^{n-1}(x)) \) dla dowolnie wybranego \( x\in X \).
Przykład
Rozważmy \( \alpha\in S_6 \) daną przez
\( \begin{array} {|c||c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline \alpha(n) & 3 & 5 & 0 & 1 & 2 & 4 \\ \hline \end{array} \)
Dowolną permutację \( \alpha \) zbioru \( X \) można rozłożyć na rozłączne cykle w sposób następujący:
Dowód
Dla dowodu poprawności algorytmu rozkładu pokażemy najpierw, że iteracja w drugim punkcie zawsze osiąga element wyjściowy \( x \). Ponieważ zbiór \( X \) jest skończony iteracja \( x,\alpha(x),\alpha^2(x)\ldots \) w pewnym kroku musi wrócić do elementu już rozważanego, zatem \( \alpha^i(x)=\alpha^j(x) \) dla pewnych \( i < j \). Weźmy najmniejsze takie \( j \), że \( \alpha^i(x)=\alpha^j(x) \) dla pewnego \( 0\leq i < j \). Gdyby \( i\neq 0 \) to z faktu, że \( \alpha \) jest permutacją mamy \( \alpha^{i-1}(x)=\alpha^{j-1}(x) \), co stoi w sprzeczności z minimalnością \( j \). A zatem \( \alpha^j(x)=x \).
Pozostaje jeszcze pokazać, że otrzymane cykle są rozłączne. Załóżmy, że nie są i weźmy pierwszy napotkany element \( y=\alpha^i(x) \), który był już w którymś z poprzednich cykli. Zauważmy, że \( i>0 \) gdyż \( x \) był wybrany jako element nie pokryty przez żaden cykl (patrz punkt pierwszy). Wiemy, że istnieje element \( z \) w tym samym cyklu co \( y \) taki, że \( \alpha(z)=y \), ale także \( \alpha(\alpha^{i-1}(x))=y \). Ponieważ \( \alpha \) jest permutacją, otrzymujemy \( \alpha^{i-1}(x)=z \), co stoi w sprzeczności z faktem, że \( y \) jest jedynym elementem z poprzedniego cyklu.
Jeśli permutacja \( \alpha \) złożona jest z \( k \) rozłącznych cykli, to zapisujemy \( \alpha=(x_0,\ldots)(x_1,\ldots)\ldots(x_{k-1},\ldots) \), gdzie w kolejnych nawiasach są elementy kolejnych cykli startujące od odpowiednio: \( x_0,\ldots,x_{k-1} \).
Przykład
Rozważmy jeszcze raz permutację \( \alpha\in S_7 \):
\( \begin{array} {|c||c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \alpha(n) & 2 & 3 & 6 & 0 & 4 & 1 & 5 \\ \hline \end{array} \)
Rozkład \( \alpha \) na cykle: