Permutacja

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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]

Information icon.svg 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]

Information icon.svg 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]

Information icon.svg Osobny artykuł: funkcja odwrotna.

Permutacja odwrotna \pi^{-1} do permutacji \pi\in S_n, która odwzorowuje w zapisie macierzowym wiersz górny na dolny, to permutacja odwzorowująca dolny wiersz na górny: aby uzyskać macierz w zapisie macierzowym należy zamienić porządek wierszy i (dla wygody) uporządkować rosnąco kolumny.

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

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 pewnej liczby cykli.

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

\pi^n=p_1^n\circ p_2^n\circ \ldots \circ p_k^n, 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