Czym są permutacje?

Archiwum kompendium.
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 5843
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2387 razy
Pomógł: 643 razy

Czym są permutacje?

Post autor: mol_ksiazkowy » 19 sty 2008, o 03:19

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 n kąta foremnego, etc. El. neutralny e, to permutacja identycznościowa. itd. Warto zapamiętać te użyteczną formułke: Permutacja to ustawienie obok siebie - w dowolnej kolejnosci liczb 1, ...,n.


*Ten skończony zbiór dla wygody ,- (model) bierzemy sobie \(\displaystyle{ S=\{1, ...n\}}\). Permutację \(\displaystyle{ p 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 a t. że \(\displaystyle{ p(a)=a}\), tj p. 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 q 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 j}\) mamy: \(\displaystyle{ p(i)=j , \ p(j)=i}\) oraz \(\displaystyle{ p(a)=a}\) gdy \(\displaystyle{ a i \ a 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łaczne, jeśli warunek \(\displaystyle{ p(j)= j}\) pociąga \(\displaystyle{ q(j) 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 odwzor. 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 permutacją 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 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 p. nieparzystą. (tj. \(\displaystyle{ sgn(p)=-1}\)). w przeciwnym razie jest ona p. parzystą, (tj. \(\displaystyle{ sgn(p)=1}\)).



Tw Cayleya
Kazdą grupę rzędu 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 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 X \}}\) to zbiór łuków. Zbiór cykli digrafu \(\displaystyle{ D(p)}\) zwie się kanonicznym rozkładem p. I tak np dla permutacji T ma on postać \(\displaystyle{ [3,6] [1,7,5,4] [2]}\). Mówimy, że \(\displaystyle{ p S_n}\) jest typu \(\displaystyle{ \lambda= }\), jesli w jej rozkł. 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= }\). Dla p. typu \(\displaystyle{ \lambda= }\) 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łądzie kanonicznym mają k cykli jest równa wartości bezwzględnej liczby \(\displaystyle{ s(n,k)}\) tzw. liczby Stirlinga


ODPOWIEDZ