Permutacja

Z Wikipedii

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ń

Ten szablon: pokaż • dyskusja • edytuj

Permutacja – wzajemnie jednoznaczne przekształcenie pewnego zbioru na siebie. Najczęściej termin ten jest używany w odniesieniu do permutacji zbiorów skończonych.

Permutacje zbiorów skończonych mogą być utożsamiane z ustawianiem elementów zbioru w pewnej kolejności.

Spis treści

1 Oznaczenia
2 Grupa permutacji
- 2.1 Składanie permutacji
- 2.2 Permutacja odwrotna
3 Znak permutacji
4 Cykle
5 Kombinatoryka
- 5.1 Permutacja bez powtórzeń
- 5.2 Permutacja z powtórzeniami
6 Przypisy
7 Zobacz też

[edytuj] Oznaczenia

W literaturze matematycznej istnieje szereg różnych systemów oznaczeń używanych w kontekście permutacji.

Gleichgewicht^[1] wprowadza symbol $S (X)$ na oznaczenie rodziny wszystkich permutacji zbioru X. Gdy $X=\{1,2,\ldots,n\}$ , to zamiast $S (X)$ pisze on $S n$ . Ten ostatni symbol jest także używany przez Langa^[2]. Natomiast Komorowski^[3] używa oznaczeń $Bij(X, X)$ , $Π(n)$ na $S (X)$ , $S n$ odpowiednio.

Wśród innych oznaczeń spotyka się również $\mathfrak{S}(X)$ , $Σ n$ oraz $Sym(X)$ . Ostatni rodzaj oznaczeń jest używany szczególnie w odniesieniu do zbiorów nieskończonych.

Poniżej będziemy używać symboli $S (X)$ i $S n$ które są najbardziej popularne w podręcznikach szkolnych i akademickich. Dla $\pi\in S_n$ napiszemy

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

gdy permutacja $π$ spełnia $π(i) = a i$ (dla $i=1,\ldots,n$ ), czyli gdy liczbie $i$ przypisywana jest liczba $a i$ .

[edytuj] Grupa permutacji

Zobacz więcej w osobnym artykule: grupa permutacji.

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

$S(X)\longrightarrow S_n:\pi\mapsto f^{-1}\circ\pi\circ f$

jest izomorfizmem grup. Ten sam argument pokazuje, że jeśli zbiory X i Y są równoliczne, to grupy $S (X), S (Y)$ są izomorficzne.

Moc zbioru wszystkich permutacji zbioru $n$ -elementowego, czyli rząd grupy $| S n |$ wynosi $n!$ , gdzie wykrzyknik oznacza silnię. Często używa się również oznaczenia $P n = | S n |$ .

[edytuj] Składanie permutacji

Zobacz więcej w osobnym artykule: 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 przez

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

[edytuj] Permutacja odwrotna

Zobacz więcej w osobnym artykule: funkcja odwrotna.

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

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

[edytuj] Znak permutacji

Okazuje się, że 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 np 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ą, zaś jeśli ma ona nieparzystą liczbę inwersji to nazywamy ją permutacją nieparzystą.

[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ł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}$

[edytuj] Kombinatoryka

[edytuj] Permutacja bez powtórzeń

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

Definicja: Permutacją bez powtórzeń zbioru złożonego z n roż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: $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).

Przypisy

↑ Gleichgewicht, Bolesław: Algebra. Podręcznik dla kierunków nauczycielskich studiów matematycznych, Państwowe Wydawnictwo Naukowe, Warszawa 1983. Wydanie III. Strony 35-37. ISBN 83-01-03903-5
↑ Lang, Serge: Algebra. Tłumaczenie: Ryszard Bittner. Państwowe Wydawnictwo Naukowe, Warszawa 1973. Strona 70.
↑ Komorowski, Jacek: Od liczb zespolonych do tensorów, spinorów, algebr Liego i kwadryk, Państwowe Wydawnictwo Naukowe, Warszawa 1978. Strony 2-3.

[edytuj] Zobacz też

Kategorie: Teoria grup • Kombinatoryka

We provide Linux to the World