Rozważając permutacje zbiorów \( n \)-elementowych wystarczy ograniczyć się do permutacji zbioru \( \mathbb{Z}_n \). Każdy inny taki zbiór różni się bowiem od \( \mathbb{Z}_n \) jedynie nazwami elementów.
Poznaliśmy już algorytm rozkładu permutacji na rozłączne cykle. Przystąpmy do klasyfikacji permutacji względem struktury takiego rozkładu. Przypomnijmy, że rozkład permutacji na cykle jest jednoznaczny z dokładnością do kolejności, tzn. jeśli \( \sigma_1 \circ \ldots \circ \sigma_k = \pi_1 \circ \ldots \circ \pi_l \) są dwoma rozkładami tej samej permutacji na cykle to \( k=l \) i \( {\{ {\sigma_1,\ldots,\sigma_k} \} } = {\{ {\pi_1,\ldots,\pi_k} \} } \).
Pierwszym ważnym niezmiennikiem dla permutacji \( \pi\in S_n \) jest:
Liczba cykli permutacji \( \pi\in S_n \) zdefiniowana jako liczba cykli w jamimkolwiek rozkładzie \( \pi \) na cykle.
Jednoznaczność rozkładu na cykle pozwala nam zdefiniować również drugi ważny niezmiennik.
Typ permutacji \( \pi\in S_n \) to wektor \( (\alpha_1,\ldots,\alpha_n) \), gdzie \( \alpha_i \) jest liczbą \( i \)-elementowych cykli w rozkładzie \( \pi \). Zazwyczaj typ permutacji zapisujemy jako \( [1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}] \), przy czym często pomijamy te wartości, dla których \( \alpha_i=0 \).
Przykład
Dla permutacji \( \pi\in S_7 \) zadanej przez
\( \begin{array} {c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \pi(n) & 3 & 6 & 2 & 4 & 0 & 5 & 1 \end{array} \)
mamy:
Z samej definicji typu permutacji natychmiast wynika:
Obserwacja 6.1
Dla \( \pi\in S_n \) typu \( (\alpha_1,\ldots,\alpha_n) \) zachodzi
Obserwacja 6.2
Liczba permutacji w \( S_n \) typu \( (\alpha_1,\ldots,\alpha_n) \) to
\( \frac{n!}{1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}\alpha_1!\ldots\alpha_n!}. \)
Dowód
Potraktujmy permutację typu \( (\alpha_1,\ldots,\alpha_n) \), jako uzupełnienie elementami z \( \mathbb{Z}_n \) następującego wzorca:
\( \underbrace{(\bullet)\ldots(\bullet)}_{\alpha_1\ razy} \underbrace{(\bullet\bullet)\ldots(\bullet\bullet)}_{\alpha_2\ razy}\ldots\ldots \underbrace{(\bullet\ldots\bullet)}_{\alpha_n\ razy\ (\alpha_n\leq 1)}. \)
W miejsce \( k \) kropek możemy wstawić \( k \)-elementów na \( k! \) sposobów. Jednak w ten sposób otrzymamy wielokrotnie te same permutacje. Każdy cykl \( i \)-elementowy możemy zadać na \( i \) sposobów (rozpoczynając od różnych elementów). Dodatkowo, zwróćmy uwagę, że w naszym wzorcu dopuszczamy różną kolejność cykli o tej samej długości. \( \alpha_i \) takich samych cykli \( i \)-elementowych może być wybranych na \( \alpha_i! \) sposobów. Podsumowując, aby otrzymać liczbę permutacji typu \( \alpha_1,\ldots,\alpha_n) \) musimy, dla wszystkich \( i\in{\{ {1,\ldots,n} \} } \), podzielić \( n! \) przez długość każdego cyklu z osobna, tzn. dla każdego cyklu długości \( i \) podzielić przez \( i \), oraz przez silnię liczby \( i \)-elementowych cykli. Zatem szukana liczba to \( \frac{n!}{1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}\alpha_1!\ldots\alpha_n!} \).
Przykład
Lista typów wszystkich permutacji z \( S_3 \):
\( \begin{array} {|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & \textrm{rozklad na cykle} & \textrm{typ} \\ \hline \pi_0 & 0 & 1 & 2 & (0)(1)(2) & [1^3] \\ \pi_1 & 1 & 0 & 2 & (0,1)(2) & [1^12^1] \\ \pi_2 & 0 & 2 & 1 & (0)(12) & [1^12^1] \\ \pi_3 & 1 & 2 & 0 & (0,1,2) & [3^1] \\ \pi_4 & 2 & 0 & 1 & (0,2,1) & [3^1] \\ \pi_5 & 2 & 1 & 0 & (0,2)(1) & [1^12^1] \\ \hline \end{array} \)
Liczba permutacji z \( S_3 \) o kolejnych typach:
\( \begin{array} {|c|l|} \hline \hbox{\rm typ} & \hbox{\rm liczba permutacji} \\ \hline 1^3 & \frac{3!}{1^3\cdot3!}=1 \\ 1^1 2^1 & \frac{3!}{1^1\cdot2^1\cdot1!\cdot1!}=3 \\ 3^1 & \frac{3!}{3^1\cdot1!}=2 \\ \hline \end{array} \)
Jak zobaczymy za chwilę, typ permutacji jest zachowywany przez pewną bardzo ważną operację algebraiczną.
Permutacja sprzężona do permutacji \( \pi,\rho\in S_n \) to każda permutacja postaci \( \sigma\pi\sigma^{-1} \), gdzie \( \sigma\in S_n \).
Oczywiście, jeśli \( \sigma\pi\sigma^{-1}=\rho \) to \( \pi=\sigma^{-1}\rho\sigma \). Zatem dwuargumentowa relacja sprzężenia jest symetryczna. Łatwo udowodnić (jako ćwiczenie), że relacja ta jest również zwrotna i przechodnia oraz, że jedyną permutacją sprzeżoną do permutacji identycznościowej \( id \) jest ona sama.
Obserwacja 6.3
Permutacje \( \pi,\rho\in S_n \) mają ten sam typ wtedy i tylko wtedy, gdy są sprzężone.
Załóżmy najpierw, że \( \pi \) i \( \rho \) są sprzężone, czyli że \( \sigma\pi\sigma^{-1}=\rho \) dla pewnego \( \sigma \). Rozważmy jakiś cykl \( (x_0,\ldots,x_{k-1}) \) permutacji \( \pi \). Wtedy \( (\sigma(x_0),\ldots,\sigma(x_{k-1})) \) jest cyklem permutacji \( \rho \). Istotnie, dla \( i = 0,\ldots,k-1 \) mamy:
i podobnie:
Każdy zatem cykl permutacji \( \pi \) wyznacza jednoznacznie cykl permutacji \( \rho \) o tej samej liczności. Tym samym \( \pi \) i \( \rho \) są tego samego typu.
Dla dowodu w drugą stronę załóżmy, że \( \pi \) i \( \rho \) mają ten sam typ. Wtedy możemy określić bijekcję przyporządkowującą każdemu cyklowi permutacji \( \pi \) pewien cykl \( \rho \) o tej samej długości. Po rozkładzie obu permutacji \( \pi,\rho \) na rozłączne cykle i nasza bijekcja między cyklami przyporzadkowuje cyklowi \( (x_0,\ldots,x_{k-1}) \) cykl \( (y_0,\ldots,y_{k-1}) \), definiujemy \( \sigma \in S_n \) kładąc \( \sigma(x_i)=y_i \). Łatwo sprawdzić, że wtedy \( \sigma\pi\sigma^{-1}=\rho \).
Transpozycja to permutacja w \( S_n \) (dla \( n\leq2 \)) typu \( [1^{n-2}2^1] \). Innymi słowy, transpozycja dokonuje tylko jednego przestawienia dwóch elementów ze zbioru \( n \)-elementowego.
Przykład
Dla permutacji \( \pi\in S_7 \) zadanej przez
mamy:
Waga transpozycji wynika z faktu, że dowolna permutacja jest złożeniem transpozycji. Ponieważ, dowolna permutacja jest rozkładalna na cykle wystarczy pokazać, że każdy cykl jest złożeniem transpozycji.
Obserwacja 6.4
Dowolny cykl z \( S_n \) jest złożeniem \( n-1 \) transpozycji.
Dowód
Cykl \( \pi=(x_0,\ldots,x_{n-1}) \) można przedstawić tabelką:
\( \begin{array} {|c||c|c|c|c|c|c|} \hline n & x_0 & x_1 & x_2 & \ldots & x_{n-2} & x_{n-1} \\ \hline \pi(n) & x_1 & x_2 & x_3 & \ldots & x_{n-1} & x_0 \\ \hline \end{array} \)
Zauważmy, że \( \pi \) jest następującym złożeniem transpozycji
\( (x_0,x_{n-1})(x_0,x_{n-2})\ldots(x_0,x_2)(x_0,x_1). \)
Rzeczywiście \( x_0 \) przejdzie:
Podobnie \( x_1 \) przejdzie
Ogólnie, \( x_i \) (dla \( i\in{\{ {1,\ldots,n-2} \} } \))
\( (x_0,x_1),(x_0,x_2),\ldots,(x_0,x_{i-1}) \),
Natomiast \( x_{n-1} \) zostanie przesunięte dopiero ostatnią transpozycją i przyjmie wartość \( x_0 \).
Wniosek 6.5
Dowolna permutacja jest złożeniem transpozycji. W szczególności każda permutacja typu \( [1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}] \) ma rozkład na co najwyżej \( \alpha_2+2\alpha_3+\ldots(n-1)\alpha_n \) transpozycji.
Przykład
Dla permutacji \( \pi\in S_7 \) zadanej przez
mamy
Zauważmy, że składanie transpozycji na rozłącznych zbiorach dwuelementowych jest przemienne. Na ogół jednak, ponieważ transpozycje nie działają na zbiorach rozłącznych, to nie możemy ich dowolnie przestawiać. W naszym przykładzie transpozycje generujące dwa różne cykle są parami rozłączne, więc ich kolejność jest bez znaczenia. Między innymi dlatego istnieje wiele rozkładów na transpozycje. Ale nie tylko dlatego - mamy bowiem również \( \pi=(1,6)(2,5)(0,2)(3,6)(0,5)(4,6)(2,5) \).
Nie mamy zatem jednoznaczności rozkładu na transpozycje, tak jak to miało miejsce przy rozkładzie na cykle. Nawet liczba transpozycji nie musi być ta sama w różnych rozkładach na transpozycje. Zobaczymy jednak, że nie zmienia się parzystość liczby transpozycji w rozkładzie.
Obserwacja 6.6
Jeśli \( \pi,\tau \in S_n \) i \( \tau \) jest transpozycją, to
\( c(\tau\pi)=c(\pi)\pm 1=c(\pi\tau). \)
Dowód
Udowodnimy tylko pierwszą równość. Załóżmy, że \( \tau=(a,b) \) tzn., \( \tau(a)=b \), \( \tau(b)=a \) i \( \tau(x)=x \) dla wszystkich pozostałych elementów \( x \in\mathbb{Z}_n \). Rozumowanie dzielimy na dwa przypadki:
Wtedy \( \tau\pi=(a,x,\ldots,y)(b,w,\ldots,z)\ldots \), gdzie ostatni wielokropek oznacza pozostałe cykle permutacji \( \pi \). Zatem w tym przypadku mamy \( c(\tau\pi)=c(\pi)+1 \).
Wtedy \( \tau\pi=(a,x,\ldots,y,b,\ldots,z)\ldots \). Mamy więc \( c(\tau\pi)=c(\pi)-1 \).
Obserwacja 6.7
Jeśli permutacja jest przedstawialna jako złożenia \( r \) i \( r' \) transpozycji, to liczby \( r \) i \( r' \) albo są obie parzyste albo obie nieparzyste.
Dowód
Niech \( \tau_{r-1}\ldots\tau_0=\tau_{r'-1}'\ldots\tau_0' \) będą dwoma rozkładami tej samej permutacji \( \pi \in S_n \) na transpozycje. Na mocy Obserwacji 6.6 mamy:
\( c(\tau_{r-1}\ldots\tau_0) = c(\tau_{r-2}\ldots\tau_0) \pm 1 = c(\tau_{r-3}\ldots\tau_0) \pm 1 \pm 1 = \ldots = c(\tau_0) \underbrace{\pm 1 \pm 1 \ldots \pm 1}_{r-1 \ razy} \)
Niech \( t \) opisuje iloć dodawań jedynki w powyższej formule. Wtedy \( r-1-t \) to liczba odejmowań jedynki. Transpozycja \( \tau_0 \) ma \( 1 \) cykl \( 2 \)-elementowy i \( n-2 \) cykli \( 1 \)-elementowych, czyli \( c(\tau_0)=1+(n-2)=n-1 \). Zatem
\( c(\pi)=c(\tau_{r-1}\ldots\tau_0)=n-1+t-(r-1-t)=n-r+2t \)
dla pewnego \( t \). Analogicznie
\( c(\pi)=c(\tau'_{r'-1}\ldots\tau'_0)=n-1+t'-(r'-1-t')=n-r'+2t' \)
dla pewnego \( t' \). Porównując obydwa wyniki otrzymujemy
\( r-r'=2a-2a', \)
czyli różnica \( r-r' \) jest zawsze parzysta.
Obserwacja 6.7 pozwala zdefiniować parzystość permutacji.
Permutacja parzysta to permutacja będąca złożeniem parzystej liczby transpozycji.
Permutacja nieparzysta to permutacja będąca złożeniem nieparzystej liczby transpozycji.
Znak permutacji \( \pi \) to \( \mbox{\sf sgn}(\pi)=(-1)^r \), gdzie \( r \) jest liczbą transpozycji, na które można rozłożyć \( \pi \).
Obserwacja 6.8
Dla dowolnych \( \pi,\sigma\in S_n \)
Dowód
Identyczność jest złożeniem zera transpozycji. Drugi punkt wynika natychmiast z Obserwacji 6.6. Dla dowodu trzeciego odnotujmy tylko, że \( \mbox{\sf sgn}(\pi)\cdot\mbox{\sf sgn}(\pi^{-1}) =\mbox{\sf sgn}(\pi\pi^{-1})=\mbox{\sf sgn}(id_{\mathbb{Z}_n})=1 \).
Przykład
Dla relaksu rozważmy łamigłówkę logiczną rozgrywaną na kwadracie \( 3 \times 3 \). Wszystkie pola, poza prawym dolnym, wypełnione są kwadratowymi klockami z różnymi literami B,O,R,L,Y,M,E,P. Prawe dolne pole jest puste - oznaczamy go przez "". Celem gry jest ułożenie napisu "PROBLEMY_". Dopuszczalnym ruchem jest przesunięcie klocka sąsiadującego z pustym polem na to właśnie pole. Czy z pozycji "BORLYMEP_" można ułożyć napis "PROBLEMY_"?
Zauważmy, że pozycja startowa i końcowa mają puste pole "-" w tym samym miejscu. To oznacza, że wykonując roszadę bloków musimy wykonać tyle samo przesunięć do góry co w dół i tyle samo przesunięć w prawo co w lewo. To z kolei oznacza, że potencjalna ilość ruchów wiodących do rozwiązania musi być parzysta. Tłumacząc nasz problem na język permutacji odnotujmy, że:
przy czym nie wszystkie transpozycje są dopuszczalne.
Zauważmy, że
Ponieważ nie można złożyć nieparzystej permutacji z parzystej liczby transpozycji, nasza łamigłówka nie jest możliwa do rozwiązania.
Obserwacja 6.9
Dla \( n\geq2 \) w \( S_n \) jest dokładnie tyle samo permutacji parzystych co nieparzystych.
Dowód
Niech \( n\geq2 \) i \( \pi_0,\ldots,\pi_{k-1} \) będzie listą wszystkich parzystych permutacji w \( S_n \). Ponadto, rozważmy transpozycję \( \tau=(01)(2)\ldots(n) \). Wtedy oczywiście permutacje \( \tau\pi_0,\tau\pi_1,\ldots,\tau\pi_{k-1} \) są parami różne, gdyż jeśli \( \tau\pi_i=\tau\pi_j \) to \( \pi_i=\tau^{-1}\tau\pi=\tau^{-1}\tau\pi_j=\pi_j \). Ponadto dowolna \( \tau\pi \) jest nieparzysta, bo \( \mbox{\sf sgn}(\tau\pi)=\mbox{\sf sgn}(\tau)\mbox{\sf sgn}(\pi)=(-1)\cdot1=-1. \) Pozostaje pokazać, że dowolna nieparzysta permutacja \( \rho \) jest na liście \( \tau\pi_0,\tau\pi_1,\ldots,\tau\pi_{k-1} \). Ponieważ \( \mbox{\sf sgn}(\tau^{-1}\rho)=\mbox{\sf sgn}(\tau^{-1})\mbox{\sf sgn}(\rho)=(-1)\cdot(-1)=1, \) to \( \tau^{-1}\rho \) jest permutacją parzystą, a zatem jest postaci \( \pi_i \) dla pewnego \( i \). To zaś oznacza, że
\( \rho=\tau\tau^{-1}\rho=\tau\pi_i, \)
czyli \( \rho \) jest na liście \( \tau\pi_0,\tau\pi_1,\ldots,\tau\pi_{k-1} \). Uzyskana bijekcja \( \pi_i \mapsto \tau\pi_i \) dowodzi naszej obserwacji.