Permutacja

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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 Stirlinga
liczby Bella
liczby Eulera

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

edytuj ten szablon

Definicja intuicyjna:
Permutacja – uporządkowanie elementów zbioru, inaczej ustawienie ich w pewnej kolejności.

Permutacja – wzajemnie jednoznaczne przekształcenie pewnego zbioru skończonego na siebie.

Zbiór wszystkich permutacji zbioru $n$ elementowego oznaczamy $Σ n$ – wraz z działaniem składania funkcji tworzy on grupę permutacji. Permutacja zbioru $n$ elementowego jest izomorficzna z permutacją zbioru $\{1,2,\ldots,n\}$ , gdzie n jest liczbą elementów zbioru. Wystarczy zauważyć, że z równoliczności obu zbiorów wynika istnienie bijekcje jednego z nich na drugi – możemy ponumerować elementy zbioru liczbami $(1,2,\ldots,n).$

Liczba wszystkich permutacji zbioru $n$ elementowego wynosi $\! P_n=n!$ , gdzie wykrzyknik oznacza silnię.

Czasem pojęcia permutacji używa się również w stosunku do zbiorów nieskończonych.

Spis treści

1 Zapis
2 Znak permutacji
3 Składanie permutacji
4 Permutacja odwrotna
5 Cykle
6 Permutacje a kombinatoryka
- 6.1 Permutacja bez powtórzeń
- 6.2 Permutacja z powtórzeniami
7 Zobacz też

[edytuj] Zapis

Symbol: $\pi=\begin{pmatrix} 1 & 2 & \ldots & n \\ a_1 & a_2 & \ldots & a_n \end{pmatrix}$ oznacza permutację $π$ taką, że $π(i) = a i$ . Liczbie $i$ przypisywana jest liczba $a i$ .

[edytuj] Znak permutacji

Okazuje się, że daną permutację można otrzymać za pomocą złożenia różnych ilości przestawień (transpozycji) par elementów (permutacja nie jest jednoznacznie rozkładalna na transpozycje). Niezmiennikiem pozostaje jednak parzystość liczby transpozycji. 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ą, zaś jeśli ma ona nieparzystą liczbę inwersji to nazywamy ją permutacją nieparzystą.

[edytuj] Składanie permutacji

Zobacz więcej w osobnym artykule: złożenie funkcji.

Permutacje składamy tak jak wszystkie inne funkcje. Złożeniem permutacji $π 1 (i)$ i $π 2 (i)$ jest permutacja $(\pi_2\circ\pi_1)(i)=\pi_2(\pi_1(i))$

Przykład:

$\pi=(\pi_2\circ\pi_1)=\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 \\ 3 & 1 & 2 \end{pmatrix}$

[edytuj] Permutacja odwrotna

Permutację odwrotną do permutacji $π$ czyli permutację $π - 1$ konstruujemy poprzez zamianę wierszy w powyższym zapisie i uporządkowanie ("posortowanie" po "górnym" elemencie) kolumn.

Przykład:

$\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}$

[edytuj] Cykle

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 $π$ na k rozłącznych cykli.

Przykład:

Cyklem jest:

$\begin{pmatrix} 1 & 3 & 5 & 8 & 2 & 4 & 6 & 7 \\ 3 & 5 & 8 & 1 & 2 & 4 & 6 & 7 \end{pmatrix}$ co zapisujemy 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}$

[edytuj] Permutacje a kombinatoryka

[edytuj] Permutacja bez powtórzeń

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

Przykład: Elementy zbioru $A = {a, b, c}$ można ustawić w ciąg na $P 3 = 3! = 6$ sposobów: ${a b c, a c b, b a c, b c a, c a b, c b a}$ .

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

[edytuj] Permutacja z powtórzeniami

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