Permutacja

Permutacja (łac. permutatio „zmiana, wymiana”) – wzajemnie jednoznaczne przekształcenie pewnego zbioru na siebie. Najczęściej termin ten oznacza funkcję na zbiorach skończonych.

Permutacje zbiorów skończonych mogą być utożsamiane z ustawianiem elementów zbioru w pewnej kolejności^[1]. W poniższym artykule zbiór wszystkich permutacji zbioru X {\displaystyle X} będzie oznaczany S ( X ) , {\displaystyle S(X),} jeżeli X = { 1 , 2 , 3 , … , n } , {\displaystyle X=\{1,2,3,\dots ,n\},} to zapisywany on będzie symbolem S n {\displaystyle S_{n}} (zob. pozostałe oznaczenia w artykule o grupach permutacji).

Dla permutacji zbiorów skończonych stosuje się specjalne oznaczenia. Niech π ∈ S n , {\displaystyle \pi \in S_{n},} wówczas zapisuje się ją jako

π = ( 1 2 … n a 1 a 2 … a n ) , {\displaystyle \pi ={\begin{pmatrix}1&2&\dots &n\\a_{1}&a_{2}&\dots &a_{n}\end{pmatrix}},}

gdzie a i = π ( i ) {\displaystyle a_{i}=\pi (i)} dla i = 1 , … , n . {\displaystyle i=1,\dots ,n.}

Permutację π ∈ S n {\displaystyle \pi \in S_{n}} można też zapisać^[2] jako macierz A , {\displaystyle A,} dla której A i , j π = { 1 , dla  π ( i ) = j , 0 , dla  π ( i ) ≠ j . {\displaystyle A_{i,j}^{\pi }={\begin{cases}1,&{\text{dla }}\pi (i)=j,\\0,&{\text{dla }}\pi (i)\neq j\end{cases}}.} Alternatywnie jako macierz B i , j π = { 1 , dla  π ( j ) = i , 0 , dla  π ( j ) ≠ i . {\displaystyle B_{i,j}^{\pi }={\begin{cases}1,&{\text{dla }}\pi (j)=i,\\0,&{\text{dla }}\pi (j)\neq i\end{cases}}.}

Oba przyporządkowania różnią się o transpozycję wynikowej macierzy, tzn. dla dowolnej π ∈ S n {\displaystyle \pi \in S_{n}} mamy, że A π = ( B π ) T . {\displaystyle A^{\pi }=(B^{\pi })^{T}.}

Reprezentacja w postaci S n ∋ π → B π ∈ G L ( n ) {\displaystyle S_{n}\ni \pi \to B^{\pi }\in GL(n)} jest izomorfizmem grupy S n {\displaystyle S_{n}} z operacją składania funkcji na odpowiednią podgrupę grupy macierzy n × n {\displaystyle n\times n} z operacją mnożenia macierzy, tzn.:

B σ ∘ π = B σ ⋅ B π {\displaystyle B^{\sigma \circ \pi }=B^{\sigma }\cdot B^{\pi }}

dla dowolnych π , σ ∈ S n {\displaystyle \pi ,\sigma \in S_{n}}

Reprezentacja w postaci macierzy A π {\displaystyle A^{\pi }} jest bijektywnym antyhomomorfizmem:

A σ ∘ π = A π ⋅ A σ {\displaystyle A^{\sigma \circ \pi }=A^{\pi }\cdot A^{\sigma }}

Na przykład dla permutacji π = ( 1 2 3 4 5 1 4 2 5 3 ) {\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}} mamy, postacie macierzowe A π = ( 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 ) {\displaystyle A^{\pi }={\begin{pmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{pmatrix}}}

oraz

B π = ( 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 ) . {\displaystyle B^{\pi }={\begin{pmatrix}1&0&0&0&0\\0&0&1&0&0\\0&0&0&0&1\\0&1&0&0&0\\0&0&0&1&0\end{pmatrix}}.}

Zbiór S ( X ) {\displaystyle S(X)} wszystkich permutacji zbioru X {\displaystyle X} wraz z działaniem składania funkcji stanowi grupę nazywaną grupą permutacji. Jeśli X {\displaystyle X} jest zbiorem n {\displaystyle n} -elementowym, to grupa S ( X ) {\displaystyle S(X)} jest izomorficzna z S n : {\displaystyle S_{n}{:}} niech f : { 1 , … , n } → X {\displaystyle f\colon \{1,\dots ,n\}\to X} będzie bijekcją. Wówczas odwzorowanie

S ( X ) → S n ; π ↦ f − 1 ∘ π ∘ f {\displaystyle S(X)\to S_{n};\;\pi \mapsto f^{-1}\circ \pi \circ f}

jest izomorfizmem grup. Podobnie można pokazać, że jeśli zbiory X , Y {\displaystyle X,Y} są równoliczne, to grupy S ( X ) , S ( Y ) {\displaystyle S(X),S(Y)} są izomorficzne, a więc nierozróżnialne na gruncie teorii grup.

Rząd grupy S n , {\displaystyle S_{n},} czyli moc zbioru wszystkich permutacji zbioru n {\displaystyle n} -elementowego, to możliwa liczba uporządkowań tego zbioru równa n ! , {\displaystyle n!,} gdzie wykrzyknik oznacza silnię. W kombinatoryce na oznaczenie liczności tego zbioru stosuje się również symbol P n . {\displaystyle P_{n}.}

Złożeniem permutacji π 1 , π 2 ∈ S ( X ) {\displaystyle \pi _{1},\pi _{2}\in S(X)} jest permutacja π 2 ∘ π 1 ∈ S ( X ) {\displaystyle \pi _{2}\circ \pi _{1}\in S(X)} zadana wzorem

( π 2 ∘ π 1 ) ( x ) = π 2 ( π 1 ( x ) ) {\displaystyle (\pi _{2}\circ \pi _{1})(x)=\pi _{2}{\big (}\pi _{1}(x){\big )}} dla x ∈ X . {\displaystyle x\in X.}

Przykład

( 1 2 3 3 2 1 ) ∘ ( 1 2 3 2 3 1 ) = ( 1 2 3 2 1 3 ) . {\displaystyle {\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}\circ {\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}={\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}.}

Permutacja π − 1 , {\displaystyle \pi ^{-1},} odwrotna do permutacji π ∈ S n {\displaystyle \pi \in S_{n}} odwzorowującej wiersz górny na dolny to permutacja odwzorowująca dolny wiersz na górny: aby uzyskać jej zapis, należy zamienić porządek wierszy i (dla wygody) uporządkować rosnąco kolumny.

W zapisie macierzowym, macierz permutacji π − 1 , {\displaystyle \pi ^{-1},} odwrotnej do permutacji π ∈ S n , {\displaystyle \pi \in S_{n},} to transpozycja macierzy permutacji π . {\displaystyle \pi .}

Przykład

Jeśli π = ( 1 2 3 2 1 3 ) ∈ S 3 , {\displaystyle \pi ={\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}\in S_{3},} to

π − 1 = ( 1 2 3 2 1 3 ) − 1 = ( 2 1 3 1 2 3 ) = ( 1 2 3 2 1 3 ) . {\displaystyle \pi ^{-1}={\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}^{-1}={\begin{pmatrix}2&1&3\\1&2&3\end{pmatrix}}={\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}.}

W zapisie macierzowym, ta sama permutacja π = ( 1 2 3 2 1 3 ) ∈ S 3 {\displaystyle \pi ={\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}\in S_{3}} ma macierz: A = ( 0 1 0 1 0 0 0 0 1 ) , {\displaystyle A={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}},}

a permutacja π − 1 , {\displaystyle \pi ^{-1},} odwrotna do π , {\displaystyle \pi ,} ma macierz A T = ( 0 1 0 1 0 0 0 0 1 ) T = ( 0 1 0 1 0 0 0 0 1 ) = A . {\displaystyle A^{T}={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}^{T}={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}=A.}

Znak permutacji definiuje się jako znak wyznacznika macierzy tej permutacji. Można na to spojrzeć też w inny sposób: każdą permutację można otrzymać za pomocą złożenia różnych liczb przestawień (transpozycji) par elementów. Takie przedstawienie permutacji nie jest jednoznaczne i można zmienić liczbę użytych transpozycji, niemniej jednak liczba transpozycji w takiej reprezentacji jest zawsze albo parzysta, albo nieparzysta. Inaczej mówiąc, parzystość liczby transpozycji jest niezmiennikiem tej operacji. Wynika to z faktu, że każda transpozycja zmienia całkowitą liczbę inwersji o liczbę nieparzystą. Permutację, która ma parzystą liczbę inwersji nazywamy parzystą (lub dodatnią), zaś jeśli ma ona nieparzystą liczbę inwersji, to nazywamy ją permutacją nieparzystą (lub ujemną).

Cyklem nazywamy każdą permutację postaci:

( a 1 a 2 … a k − 1 a k a k + 1 a k + 2 … a n a 2 a 3 … a k a 1 a k + 1 a k + 2 … a n ) . {\displaystyle {\begin{pmatrix}a_{1}&a_{2}&\dots &a_{k-1}&a_{k}&a_{k+1}&a_{k+2}&\dots &a_{n}\\a_{2}&a_{3}&\dots &a_{k}&a_{1}&a_{k+1}&a_{k+2}&\dots &a_{n}\end{pmatrix}}.}

Zazwyczaj, gdy operujemy na cyklach opuszczamy część: ( a k + 1 a k + 2 … a n a k + 1 a k + 2 … a n ) , {\displaystyle {\begin{pmatrix}a_{k+1}&a_{k+2}&\dots &a_{n}\\a_{k+1}&a_{k+2}&\dots &a_{n}\end{pmatrix}},} gdyż nie wnosi ona nic nowego.

Zapis cyklu możemy jeszcze uprościć. Wystarczy zauważyć, że dolny wiersz naszego symbolu oznaczającego cykl można jednoznacznie odtworzyć z górnego. Zatem nasz ostateczny uproszczony symbol przybiera postać:

( a 1 a 2 … a k − 1 a k a 2 a 3 … a k a 1 ) = ( a 1 , a 2 , … , a k ) . {\displaystyle {\begin{pmatrix}a_{1}&a_{2}&\dots &a_{k-1}&a_{k}\\a_{2}&a_{3}&\dots &a_{k}&a_{1}\end{pmatrix}}=(a_{1},a_{2},\dots ,a_{k}).}

Można udowodnić (choć jest to dość intuicyjne), że każdą permutację można przedstawić jako złożenie k {\displaystyle k} rozłącznych (niezależnych), a więc i różnych, cykli. Ponieważ cykle są różne i wszystkie należą do zbioru S n {\displaystyle S_{n}} o liczbie elementów | S n | = n ! , {\displaystyle |S_{n}|=n!,} więc k < n ! . {\displaystyle k<n!.}

Składanie permutacji, podobnie jak większości funkcji, nie jest przemienne. Nie dotyczy to sytuacji, gdy składamy permutacje rozłączne (niezależne). Ponieważ permutacjami rozłącznymi są rozłączne cykle to zachodzi następujące twierdzenie:

∀ m ∈ N + π m = p 1 m ∘ p 2 m ∘ ⋯ ∘ p k m , {\displaystyle \forall _{m\in \mathbb {N_{+}} }\pi ^{m}=p_{1}^{m}\circ p_{2}^{m}\circ \dots \circ p_{k}^{m},} gdzie π = p 1 ∘ p 2 ∘ ⋯ ∘ p k {\displaystyle \pi =p_{1}\circ p_{2}\circ \dots \circ p_{k}} jest rozkładem permutacji π {\displaystyle \pi } na k {\displaystyle k} rozłącznych cykli.

Przykłady

Cyklem jest permutacja:

( 1 3 5 8 2 4 6 7 3 5 8 1 2 4 6 7 ) {\displaystyle {\begin{pmatrix}1&3&5&8&2&4&6&7\\3&5&8&1&2&4&6&7\end{pmatrix}}} którą można zapisać jako ( 1 3 5 8 3 5 8 1 ) {\displaystyle {\begin{pmatrix}1&3&5&8\\3&5&8&1\end{pmatrix}}}

Rozkład na cykle

( 1 2 3 4 5 6 7 8 3 4 8 6 7 2 1 5 ) = ( 1 3 8 5 7 2 4 6 3 8 5 7 1 4 6 2 )   = ( 1 3 8 5 7 2 4 6 3 8 5 7 1 2 4 6 ) ∘ ( 1 3 8 5 7 2 4 6 1 3 8 5 7 4 6 2 )   = ( 1 3 8 5 7 3 8 5 7 1 ) ∘ ( 2 4 6 4 6 2 )   = ( 1 , 3 , 8 , 5 , 7 ) ∘ ( 2 , 4 , 6 ) {\displaystyle {\begin{matrix}{\begin{pmatrix}1&2&3&4&5&6&7&8\\3&4&8&6&7&2&1&5\end{pmatrix}}&=&{\begin{pmatrix}1&3&8&5&7&2&4&6\\3&8&5&7&1&4&6&2\end{pmatrix}}\\\ &=&{\begin{pmatrix}1&3&8&5&7&2&4&6\\3&8&5&7&1&2&4&6\end{pmatrix}}\circ {\begin{pmatrix}1&3&8&5&7&2&4&6\\1&3&8&5&7&4&6&2\end{pmatrix}}\\\ &=&{\begin{pmatrix}1&3&8&5&7\\3&8&5&7&1\end{pmatrix}}\circ {\begin{pmatrix}2&4&6\\4&6&2\end{pmatrix}}\\\ &=&(1,3,8,5,7)\circ (2,4,6)\end{matrix}}}

Permutacja jest szczególnym przypadkiem wariacji bez powtórzeń.

Definicja: Permutacją bez powtórzeń zbioru złożonego z n różnych elementów nazywamy każdy n wyrazowy ciąg utworzony ze wszystkich wyrazów zbioru. Wszystkich możliwych permutacji zbioru n-elementowego jest:

P n = n ! {\displaystyle P_{n}=n!}

Przykład: Elementy zbioru A = { a , b , c } {\displaystyle A=\{a,b,c\}} można ustawić w ciąg na P 3 = 3 ! = 6 {\displaystyle P_{3}=3!=6} sposobów: a b c , a c b , b a c , b c a , c a b , c b a . {\displaystyle abc,acb,bac,bca,cab,cba.}

Wyjaśnienie przykładu: W każdej z permutacji mamy do zapełnienia trzy wolne miejsca. W pierwszym z nich możemy umieścić dowolną z liter na trzy sposoby ( P n = 3 ⋅ … ) , {\displaystyle (P_{n}=3\cdot \ldots ),} na drugim dowolną spośród pozostałych jeszcze dwóch liter na dwa sposoby ( P n = 3 ⋅ 2 ⋅ … ) {\displaystyle (P_{n}=3\cdot 2\cdot \ldots )} itd. Na ostatnim miejscu musi znaleźć się ostatnia dostępna litera (element zbioru), a zatem możemy to zrobić tylko na jeden sposób. Ostatecznie otrzymujemy: P n = 3 ⋅ 2 ⋅ 1 = 3 ! {\displaystyle P_{n}=3\cdot 2\cdot 1=3!}

Niech A {\displaystyle A} oznacza zbiór złożony z k {\displaystyle k} różnych elementów A = { a 1 , a 2 , … , a k } . {\displaystyle A=\{a_{1},a_{2},\dots ,a_{k}\}.} Permutacją n {\displaystyle n} elementową z powtórzeniami, w której elementy a 1 , a 2 , … , a k {\displaystyle a_{1},a_{2},\dots ,a_{k}} powtarzają się odpowiednio n 1 , n 2 , … , n k {\displaystyle n_{1},n_{2},\dots ,n_{k}} razy, n 1 + n 2 + ⋯ + n k = n , {\displaystyle n_{1}+n_{2}+\dots +n_{k}=n,} jest każdy n {\displaystyle n} -wyrazowy ciąg, w którym elementy a 1 , a 2 , … , a k {\displaystyle a_{1},a_{2},\dots ,a_{k}} powtarzają się podaną liczbę razy.

Liczba takich permutacji z powtórzeniami wynosi n ! n 1 ! ⋅ n 2 ! ⋅ … ⋅ n k ! . {\displaystyle {\frac {n!}{n_{1}!\cdot n_{2}!\cdot \ldots \cdot n_{k}!}}.}

Przykład: Przestawiając litery b , a , b , k , a {\displaystyle b,a,b,k,a} można otrzymać 5 ! 2 ! ⋅ 2 ! ⋅ 1 ! = 30 {\displaystyle {\tfrac {5!}{2!\cdot 2!\cdot 1!}}=30} różnych napisów.

Wyjaśnienie: „Zwykłe” przestawianie liter w słowie babka spowoduje kilkukrotne powstanie identycznych wyrazów, np. zamieniając miejscami pierwszą i trzecią literę znów otrzymamy słowo babka. Należy to uwzględnić przy zliczaniu, dlatego rezultat trzeba podzielić każdorazowo przez liczbę „zbędnych” permutacji, które nie prowadzą do powstania nowych słów (ciągów uporządkowanych).

Spostrzeżenie: Można wobec tego zapisać wzór na permutację bez powtórzeń następująco: P n = n ! = n ! 1 ! ⋅ 1 ! ⋅ … ⋅ 1 ! {\displaystyle P_{n}=n!={\tfrac {n!}{1!\cdot 1!\cdot \ldots \cdot 1!}}} (każdy z elementów występuje dokładnie raz).

Urządzeniem do wyliczania cyklicznych permutacji był wynaleziony w połowie lat trzydziestych przez polskiego matematyka i kryptologa Mariana Rejewskiego cyklometr. Służył on polskiemu wywiadowi do łamania kodów niemieckiej maszyny szyfrującej Enigma^[3].

• Nieporządek

• BartłomiejB. Bzdęga BartłomiejB., Symetria w algebrze, „Delta”, luty 2019, ISSN 0137-3005 [dostęp 2024-11-03] .
• Oskar Skibski, nagrania na YouTube, kanał autorski, 28 maja 2020 [dostęp 2026-01-17] – w ramach kursu Matematyka Dyskretna, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego (MIM UW):
  • Permutacje.
  • Złożenie Permutacji.
• Signature (permutation) (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].