Permutacje

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 \rightarrow \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 \):

\( \alpha\beta,\beta\alpha \) są permutacjami \( X \),
\( \alpha^{-1} \) jest permutacją \( X \) taką, że \( \alpha\alpha^{-1}=id_{X}=\alpha^{-1}\alpha= \).

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} \)

sekwencja \( 0 \), \( \alpha(0)=3 \), \( \alpha^2(0)=1 \), \( \alpha^3(0)=5 \), \( \alpha^4(0)=4 \), \( \alpha^5(0)=2 \) pokwywa całe \( \mathbb{Z}_6 \),
zatem \( \alpha=(0,3,1,5,4,2) \) jest cyklem.

Rozkład permutacji na rozłączne cykle

Dowolną permutację \( \alpha \) zbioru \( X \) można rozłożyć na rozłączne cykle w sposób następujący:

wybierz dowolny element \( x\in X \), który nie jest jeszcze w żadnym cyklu,
iteruj permutację \( \alpha \) otrzymując kolejno: \( \alpha(x),\alpha^2(x),\alpha^3(x),\ldots \) aż do uzyskania \( \alpha^j(x)=x \),
dodaj do rozkładu cykl \( x,\ldots,\alpha^{j-1}(x) \),
jeśli w zbiorze \( X \) pozostały jeszcze elementy niepokryte przez żaden cykl, to wróć do pierwszego punktu.

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:

\( 0 \), \( \alpha(0)=2 \), \( \alpha(2)=6 \), \( \alpha(6)=5 \), \( \alpha(5)=1 \), \( \alpha(1)=3 \), \( \alpha(3)=0 \),

\( 4 \), \( \alpha(4)=4 \),

\( \alpha=(026513)(4) \).