Informatyka MIMUW

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

• 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:

1. wybierz dowolny element $x\in X$, który nie jest jeszcze w żadnym cyklu,
2. iteruj permutację $\alpha$ otrzymując kolejno: $\alpha(x),\alpha^2(x),\alpha^3(x),\ldots$ aż do uzyskania $\alpha^j(x)=x$,
3. dodaj do rozkładu cykl $x,\ldots,\alpha^{j-1}(x)$,
4. 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)$.