Permutacja


Permutacja w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

Spis treści

Zapis | edytuj kod

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

Zapis macierzowy | edytuj kod

Permutację π S n {\displaystyle \pi \in S_{n}} można też zapisać jako macierz A , {\displaystyle A,} dla której A i , j = { 1 , dla  π ( i ) = j , 0 , dla  π ( i ) j . {\displaystyle A_{i,j}={\begin{cases}1,&{\mbox{dla }}\pi (i)=j,\\0,&{\mbox{dla }}\pi (i)\neq j\end{cases}}.}

Na przykład permutację ( 1 2 3 4 5 1 4 2 5 3 ) {\displaystyle {\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}} można zapisać jako ( 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 {\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}}.}

Grupa permutacji | edytuj kod

 Osobny artykuł: Grupa permutacji.

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

Składanie permutacji | edytuj kod

 Osobny artykuł: Złożenie funkcji.

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 odwrotna | edytuj kod

 Osobny artykuł: Funkcja odwrotna.

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 | edytuj kod

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ą).

Cykle | edytuj kod

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 ilości 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}}}

Kombinatoryka | edytuj kod

Permutacja bez powtórzeń | edytuj kod

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: 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!}

Permutacja z powtórzeniami | edytuj kod

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ądzenia do wyliczania permutacji matematycznych | edytuj kod

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[1].

Przypisy | edytuj kod

  1. Joanna Wąsik, „Złamanie szyfru Enigmy przy użyciu teorii permutacji”, Instytut Matematyki Wydział Matematyki i Informatyki Uniwersytet Jagielloński. Plik w formacie PDF.
Kontrola autorytatywna (pojęcie matematyczne):
Na podstawie artykułu: "Permutacja" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy