Informatyka MIMUW

Permutacje

---

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:

• $\pi=(0,3,4)(1,6)(2)(4)=(0,3,4)(1,6)$,
• $\pi$ jest typu $[1^22^13^1]$.

Z samej definicji typu permutacji natychmiast wynika:

Obserwacja 6.1

Dla $\pi\in S_n$ typu $(\alpha_1,\ldots,\alpha_n)$ zachodzi

• $\alpha_1+\ldots+\alpha_n=c(\pi)$,
• $\alpha_1+2\alpha_2+\ldots+n\alpha_n=n$.

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{typ} & \hbox{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:

$\rho(\sigma(x_i))=\sigma\pi\sigma^{-1}\sigma(x_i)=\sigma\pi(x_i)=\sigma(x_{i+1}),$

i podobnie:

$\rho(\sigma(x_{k-1})=\sigma\pi\sigma^{-1}\sigma(x_{k-1})=\sigma\pi(x_{k-1})=\sigma(x_0).$

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

$\begin{array} {|c||c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \pi(n) & 0 & 1 & 5 & 3 & 4 & 2 & 6 \\ \hline \end{array}$

mamy:

• $\pi=(0)(1)(25)(3)(4)(6)=(25),$
• $\pi$ ma typ $[1^52^1]$,
• $\pi$ jest transpozycją.

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:

• w pierwszej transpozycji $(x_0,x_1)$ w $x_1$,
• a następne transpozycje już go nie przesuną.

Podobnie $x_1$ przejdzie

• pierwszą transpozycją $(x_0,x_1)$ w $x_0$,
• drugą $(x_0,x_2)$ w $x_2$,
• a następne transpozycje już go nie przesuną.

Ogólnie, $x_i$ (dla $i\in{\{ {1,\ldots,n-2} \} }$)

• pozostanie na swoim miejscu przez pierwsze $i-1$ transpozycji

$(x_0,x_1),(x_0,x_2),\ldots,(x_0,x_{i-1})$,

• przejdzie $i$-tą transpozycją w $x_0$,
• przejdzie $(i+1)$-szą transpozycją w $x_{i+1}$,
• po czym zostanie już nienaruszone.

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

$\begin{array} {|c||c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \pi(n) & 2 & 3 & 5 & 4 & 6 & 0 & 1 \\ \hline \end{array}$

mamy

• $\pi=(0,2,5)(1,3,4,6)$,
• $(1,3,4,6)=(1,6)(1,4)(1,3)$,
• $(0,2,5)=(0,5)(0,2)$,
• $\pi=(0,5)(0,2)(1,6)(1,4)(1,3)=(1,6)(1,4)(1,3)(0,5)(0,2)$.

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:

• $a$ i $b$ są w tym samym cyklu $(a,x,\ldots,y,b,w,\ldots,z)$ permutacji $\pi$.

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$.

• $a$ i $b$ są w różnych cyklach permutacji $\pi=(a,x\ldots,y)(b,\ldots,z)\ldots$.

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{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$

• $\mbox{sgn}(id_{\mathbb{Z}_n})=1$,
• $\mbox{sgn}(\sigma\pi)=\mbox{sgn}(\pi)\cdot\mbox{sgn}(\sigma)$,
• $\mbox{sgn}(\pi)=\mbox{sgn}(\pi^{-1})$,

Dowód

Identyczność jest złożeniem zera transpozycji. Drugi punkt wynika natychmiast z Obserwacji 6.6. Dla dowodu trzeciego odnotujmy tylko, że $\mbox{sgn}(\pi)\cdot\mbox{sgn}(\pi^{-1}) =\mbox{sgn}(\pi\pi^{-1})=\mbox{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:

• mamy dokonać permutacji $\pi\in S_9$:

$\begin{array} {ccccccccc} B & O & R & L & Y & M & E & P & \_ \\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\ P & R & O & B & L & E & M & Y & \_ \end{array}$

• każdy ruch zgodny z regułami gry to jakaś transpozycja wybranych klocków,

przy czym nie wszystkie transpozycje są dopuszczalne.

Zauważmy, że

• rozwiązanie musi być wykonane przy pomocy parzystej liczby ruchów, zatem każda permutacja dokonująca żądanej rearanżacji klocków jest parzysta
• $\pi=(B,P,Y,L)(O,R)(M,E)(\_)$,
• Wniosek 6.5 daje wtedy jednak, że $\pi$ jest złożeniem $3+1+1=5$ transpozycji, czyli $\pi$ jest permutacją nieparzystą.

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{sgn}(\tau\pi)=\mbox{sgn}(\tau)\mbox{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{sgn}(\tau^{-1}\rho)=\mbox{sgn}(\tau^{-1})\mbox{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.