Permutacja

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu kombinatoryka.




permutacja


kombinacja bez powtórzeń
kombinacja z powtórzeniami


wariacja bez powtórzeń
wariacja z powtórzeniami


liczby Bella
liczby Catalana
liczby Stirlinga
liczby Eulera


zasada szufladkowa Dirichleta
zasada włączeń i wyłączeń


Permutacjawzajemnie 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 będzie oznaczany S(X), jeżeli X = \{1, 2, 3, \dots, n\}, to zapisywany on będzie symbolem S_n (zob. pozostałe oznaczenia w artykule o grupach permutacji).

Zapis[edytuj | edytuj kod]

W celu skrócenia zapisu, szczególnie, gdy permutacji nie można zadać prostym wzorem, permutację \pi \in S_n zapisuje się jako

\pi = \begin{pmatrix} 1 & 2 & \ldots & n \\ a_1 & a_2 & \ldots & a_n \end{pmatrix} ,

gdy \pi(i) = a_i dla i = 1, \ldots, n, czyli permutacja \pi przypisuje liczbie i wartość a_i.

Zapis macierzowy[edytuj | edytuj kod]

Permutację można też zapisać jako macierz A, taką, że A_{i,j} = \begin{cases} 1, & \mbox{jeśli } i \mbox{ przechodzi na } j, \\ 0, & \mbox{w przeciwnym wypadku. } \end{cases}.

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

 Osobny artykuł: grupa permutacji.

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

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, Yrównoliczne, to grupy S(X), S(Y) są izomorficzne, a więc nierozróżnialne na gruncie teorii grup.

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

Składanie permutacji[edytuj | edytuj kod]

 Osobny artykuł: złożenie funkcji.

Złożeniem permutacji \pi_1,\pi_2\in S(X) jest permutacja \pi_2\circ\pi_1\in S(X) zadana wzorem

 (\pi_2\circ\pi_1)(x)=\pi_2(\pi_1(x)) dla x\in X.
Przykład 
\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 | edytuj kod]

 Osobny artykuł: funkcja odwrotna.

Permutacja \pi^{-1}, odwrotna do permutacji \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 \pi^{-1}, odwrotnej do permutacji \pi\in S_n, to transpozycja macierzy permutacji \pi.

Przykład 
Jeśli \pi=\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}\in S_3, to
\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 \pi=\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}\in S_3 ma macierz: A=\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix},
a permutacja \pi^{-1}, odwrotna do \pi, ma macierz 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 | edytuj kod]

Znak permutacji definiujemy 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 ilości przestawień (transpozycji) par elementów. Takie przedstawienie permutacji nie jest jednoznaczne i można zmienić ilość 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 | edytuj kod]

Cyklem nazywamy każdą permutację postaci:

\begin{pmatrix} a_1 & a_2 & \ldots & a_{k-1} & a_k & a_{k+1} & a_{k+2} & \ldots & a_n\\ a_2 & a_3 & \ldots & a_k & a_1 & a_{k+1} & a_{k+2} &  \ldots & a_n\ \end{pmatrix}.

Zazwyczaj, gdy operujemy na cyklach opuszczamy część: \begin{pmatrix}  a_{k+1} & a_{k+2} & \ldots & a_n\\ a_{k+1} & a_{k+2} &  \ldots & 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ć:

\begin{pmatrix} a_1 & a_2 & \ldots & a_{k-1} & a_k \\ a_2 & a_3 & \ldots & a_k & a_1 \end{pmatrix}=(a_1,a_2,\ldots,a_k)

Można udowodnić (choć jest to dość intuicyjne), że każdą permutację można przedstawić jako złożenie k rozłącznych (niezależnych), a więc i różnych, cykli. Ponieważ cykle są różne i wszystkie należą do zbioru S_n, o ilości elementów \#S_n=n!, więc 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:

\forall_{m\in\mathbb{N_+}}\pi^m=p_1^m\circ p_2^m\circ \ldots \circ p_k^m, gdzie \pi=p_1\circ p_2\circ \ldots \circ p_k jest rozkładem permutacji \pi na k rozłącznych cykli.
Przykłady
Cyklem jest permutacja:
\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 \begin{pmatrix} 1 & 3 & 5 & 8  \\ 3 & 5 & 8 & 1 \end{pmatrix}
Rozkład na cykle

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

Permutacja bez powtórzeń[edytuj | 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!

Przykład: Elementy zbioru A = \{a, b, c\} można ustawić w ciąg na P_3 = 3! = 6 sposobów: 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 \cdot ...), na drugim dowolną spośród pozostałych jeszcze dwóch liter na dwa sposoby (P_n=3 \cdot 2 \cdot ...), 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 \cdot 2 \cdot 1 = 3!

Permutacja z powtórzeniami[edytuj | edytuj kod]

Niech A oznacza zbiór złożony z k różnych elementów A = \{a_1, a_2, ..., a_k\}. Permutacją n elementową z powtórzeniami, w której elementy a_1, a_2, ..., a_k powtarzają się odpowiednio n_1, n_2, ..., n_k razy, n_1 + n_2 + ... + n_k = n, jest każdy n-wyrazowy ciąg, w którym elementy a_1, a_2, ..., a_k powtarzają się podaną liczbę razy.

Liczba takich permutacji z powtórzeniami wynosi \frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}.

Przykład: Przestawiając litery b, a, b, k, a można otrzymać 
\begin{matrix}\frac{5!}{2! \cdot 2! \cdot 1!}\end{matrix}= 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!=\begin{matrix}\frac{n!}{1! \cdot 1! \cdot ... \cdot 1!}\end{matrix} (każdy z elementów występuje dokładnie raz).

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