Czym są permutacje?

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Algebry.
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 6020
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2505 razy
Pomógł: 667 razy

Czym są permutacje?

Post autor: mol_ksiazkowy » 6 maja 2009, o 22:10

Definicja Permutacja jest to wzajemnie jednoznaczne odwzorowanie zbioru skończonego na siebie *. Zbiór wszystkich permutacji zbioru n- elementowego tworzy grupę ze względu na działanie składania, i zwie się grupą symetryczną stopnia n, można pisać \(\displaystyle{ (S_n, \circ)}\). Istnieja pewne dane, aby uznać ją za szczegolnie ważna w teorii struktur. Posiada pewne analogie z grupą \(\displaystyle{ D_n}\) symetrii \(\displaystyle{ n}\) kąta foremnego. Jej element neutralny to permutacja identycznościowa. Warto zapamiętać tę formułę: Permutacja jest to ustawienie obok siebie - w dowolnej kolejnosci liczb \(\displaystyle{ 1, ...,n}\).


*Ten skończony zbiór dla wygody ,- (model) bierzemy sobie \(\displaystyle{ S=\{1, ... ,n\}}\). Permutację \(\displaystyle{ p \in S_n}\) zapisuje się zwykle w postaci:

\(\displaystyle{ p= ( _{p(1) ....p(n)} ^{ \ 1 ...... n} )}\)
Zapis ten należy rozumieć, iż \(\displaystyle{ p}\) jest funkcją, która elementowi \(\displaystyle{ 1}\) przyporządkowuje \(\displaystyle{ p(1)}\), elementowi 2 \(\displaystyle{ p(2)}\), ...itd i na koniec elementowi \(\displaystyle{ n}\) element \(\displaystyle{ p(n)}\). Rzecz jasna \(\displaystyle{ p(1),....,p(n)}\) są to różne elementy ze zbioru \(\displaystyle{ S=\{1, ... ,n\}}\).
Zapis ten można uprościć, przez pominięcie kolumn zawierających elementy a t. że \(\displaystyle{ p(a)=a}\), tj punktów stałych, a wiec np. \(\displaystyle{ p= ( _{1 3 2} ^{1 2 3} )}\) pisze się \(\displaystyle{ p= ( _{3 2} ^{2 3} )}\). Jeśli \(\displaystyle{ b_1, ..., b_r}\) są różnymi elementami zbioru \(\displaystyle{ \{1, ...,n\}}\), zaś \(\displaystyle{ r \leq n}\), to permutację \(\displaystyle{ p= ( _{b_2 b_3....b_1} ^{b_1 b_2 ... b_r} )}\) nazywa się cyklem długości r.


Cykle długości 2 zwie się transpozycjami. Tak więc są to takie \(\displaystyle{ p}\), że dla pewnych \(\displaystyle{ i \neq j}\) mamy: \(\displaystyle{ p(i)=j , \ p(j)=i}\) oraz \(\displaystyle{ p(a)=a}\) gdy \(\displaystyle{ a \neq i \ a \neq j}\). Każdą permutację mozna przedstawić jednoznacznie - z dokładnością do kolejności- jako złożenie cykli rozłącznych oraz -nie zawsze jednoznacznie- jako złożenie transpozycji.
Def Permutację \(\displaystyle{ p}\) t. że, nie ma ona punktów stałych -tj takich \(\displaystyle{ j}\) że \(\displaystyle{ p(j)=j}\) zwiemy nieporządkiem,
Powiemy, że \(\displaystyle{ p}\) i \(\displaystyle{ q}\)rozłączne, jeśli warunek \(\displaystyle{ p(j)= j}\) pociąga \(\displaystyle{ q(j) \neq j}\). Powie się też, że p jest inwolucją, gdy \(\displaystyle{ p^2=e}\), i są to takie, które da się zapisać w postaci złożenia rozłącznych transpozycji.

Przykład:
\(\displaystyle{ p_1= ( _{1 4 2 3} ^{1 2 3 4} )= ( _{1 2 4 3} ^{1 2 3 4} ) \circ ( _{1 3 2 4} ^{1 2 3 4} )}\)
\(\displaystyle{ p_2= ( _{3 4 1 2} ^{1 2 3 4} )= ( _{1 4 3 2} ^{1 2 3 4} ) \circ ( _{3 2 1 4} ^{1 2 3 4} )}\)
\(\displaystyle{ p_1}\) nie jest inwolucją,
\(\displaystyle{ p_2}\) jest inwolucją,




Podgrupa \(\displaystyle{ A_n}\)
Zbiór wszystkich permutacji parzystych, tj takich, które można zapisać jako zlożenie parzystej liczby transpozycji- tworzy podgupę \(\displaystyle{ S_n}\) i oznaczamy ją \(\displaystyle{ A_n}\). Funkcja \(\displaystyle{ p \mapsto sgn(p)}\) jest homomorfizmem grupy \(\displaystyle{ S_n}\) na grupę \(\displaystyle{ \{-1, 1\}}\) -z działaniem mnożenia. Zbiór \(\displaystyle{ A_n}\) -będacy jądrem tego odwzorowania liczy \(\displaystyle{ \frac{n!}{2}}\) elementów. \(\displaystyle{ A_n}\) nazywamy grupą alternującą.


Przykład
\(\displaystyle{ q=( _{2 4 1 3} ^{1 2 3 4} )}\). Widzimy , że \(\displaystyle{ q(1)=2, \ q(2)=4, \ q(4)=3, \ q(3)=1}\), a więc \(\displaystyle{ q}\) jest cyklem, jest to permutacja nieparzysta. a także \(\displaystyle{ q^{-1}=( _{3 1 4 2} ^{1 2 3 4} )}\)



Inwersja zwie sie parę \(\displaystyle{ (p(i), p(j))}\) w sytuacji, gdy \(\displaystyle{ i< j}\) i \(\displaystyle{ p(i) >p(j)}\). Wracając do przykładu powyżej dla \(\displaystyle{ q}\) łatwo widać, że istnieją trzy takie pary, tj \(\displaystyle{ (2,1), \ (4,1), \ (4,3)}\) Reguła: Jeśli \(\displaystyle{ p}\) posiada nieparzystą liczbę inwersji, to jest permutacją nieparzystą. (tj. \(\displaystyle{ sgn(p)=-1}\)). w przeciwnym razie jest ona permutacją parzystą, (tj. \(\displaystyle{ sgn(p)=1}\)).



Tw Cayleya
Kazdą grupę rzędu \(\displaystyle{ n}\) można zanurzyć w \(\displaystyle{ S_n}\), tj każda grupa skończona jest izomorficzna z pewną podgrupą grupy permutacji.


wzór na rozkład cyklu na transpozycje:
\(\displaystyle{ s=(x_1....x_r) =(x_1 x_r) \circ ...\circ (x_1 x_2)}\)
Uwaga
Oba Zapisy: \(\displaystyle{ p= ( _{b_2 b_3....b_1} ^{b_1 b_2 ... b_r} )}\) i \(\displaystyle{ s=(b_1....b_r)}\) znaczą to samo i uzywamy ich zamiennie.


Przykład
\(\displaystyle{ T=( _{7 2 6 1 4 3 5} ^{1 2 3 4 5 6 7} ) =(3,6) \circ (1, 7, 5, 4) \circ (2)}\)



Digraf każdej permutacji \(\displaystyle{ p \in S_n}\) można przyporzadkować digraf \(\displaystyle{ D(p)= (X, A)}\), gdzie X to wierzchołki (tj . elementy z \(\displaystyle{ S}\)), zaś \(\displaystyle{ A=\{(i, \sigma(i)) : i \in X \}}\) to zbiór łuków. Zbiór cykli digrafu \(\displaystyle{ D(p)}\) zwie się kanonicznym rozkładem permutacji. I tak np dla permutacji \(\displaystyle{ T}\) ma on postać \(\displaystyle{ [3,6] [1,7,5,4] [2]}\). Mówimy, że \(\displaystyle{ p \in S_n}\) jest typu \(\displaystyle{ \lambda=<\lambda_1, ...\lambda_n>}\), jesli w jej rozkładzie kanonicznym występuje \(\displaystyle{ \lambda_i}\) cykli długości \(\displaystyle{ i}\) dla \(\displaystyle{ i=1, ...,n}\). Tu np . permutacja \(\displaystyle{ T}\) jest typu \(\displaystyle{ \lambda=<1,1,0,1,0,0,0>}\). Dla permutacji typu \(\displaystyle{ \lambda=<\lambda_1, ...\lambda_n>}\) jest: \(\displaystyle{ \lambda_1+2\lambda_2+....+n\lambda_n=n}\). zaś liczba wszystkich permutacji typu \(\displaystyle{ \lambda}\) zbioru \(\displaystyle{ n}\) elementowego jest równa:
\(\displaystyle{ h(\lambda_1, ....\lambda_n)= \frac{n!}{1^{\lambda_1}....n^{\lambda_n} (\lambda_1)!....(\lambda_n)!}}\)
Liczba tych permutacji \(\displaystyle{ p\in S_n}\), które w rozkładzie kanonicznym mają \(\displaystyle{ k}\) cykli jest równa wartości bezwzględnej liczby \(\displaystyle{ s(n,k)}\) tzw. liczby Stirlinga
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

ODPOWIEDZ