Czym są permutacje?

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

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ć \((S_n, \circ)\). Istnieja pewne dane, aby uznać ją za szczegolnie ważna w teorii struktur. Posiada pewne analogie z grupą \(D_n\) symetrii \(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 \(1, ...,n\). *Ten skończony zbiór dla wygody ,- (model) bierzemy sobie \(S=\{1, ... ,n\}\). Permutację \(p \in S_n\) zapisuje się zwykle w postaci: \(p= ( _{p(1) ....p(n)} ^{ \ 1 ...... n} )\) Zapis ten należy rozumieć, iż \(p\) jest funkcją, która elementowi \(1\) przyporządkowuje \(p(1)\), elementowi 2 \(p(2)\), ...itd i na koniec elementowi \(n\) element \(p(n)\). Rzecz jasna \(p(1),....,p(n)\) są to różne elementy ze zbioru \(S=\{1, ... ,n\}\). Zapis ten można uprościć, przez pominięcie kolumn zawierających elementy a t. że \(p(a)=a\), tj punktów stałych, a wiec np. \(p= ( _{1 3 2} ^{1 2 3} )\) pisze się \(p= ( _{3 2} ^{2 3} )\). Jeśli \(b_1, ..., b_r\) są różnymi elementami zbioru \(\{1, ...,n\}\), zaś \(r \leq n\), to permutację \(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 \(p\), że dla pewnych \(i \neq j\) mamy: \(p(i)=j , \ p(j)=i\) oraz \(p(a)=a\) gdy \(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ę \(p\) t. że, nie ma ona punktów stałych -tj takich \(j\) że \(p(j)=j\) zwiemy nieporządkiem, Powiemy, że \(p\) i \(q\)rozłączne, jeśli warunek \(p(j)= j\) pociąga \(q(j) \neq j\). Powie się też, że p jest inwolucją, gdy \(p^2=e\), i są to takie, które da się zapisać w postaci złożenia rozłącznych transpozycji. Przykład: \(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} )\) \(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} )\) \(p_1\) nie jest inwolucją, \(p_2\) jest inwolucją, Podgrupa \(A_n\) Zbiór wszystkich permutacji parzystych, tj takich, które można zapisać jako zlożenie parzystej liczby transpozycji- tworzy podgupę \(S_n\) i oznaczamy ją \(A_n\). Funkcja \(p \mapsto sgn(p)\) jest homomorfizmem grupy \(S_n\) na grupę \(\{-1, 1\}\) -z działaniem mnożenia. Zbiór \(A_n\) -będacy jądrem tego odwzorowania liczy \(\frac{n!}{2}\) elementów. \(A_n\) nazywamy grupą alternującą. Przykład \(q=( _{2 4 1 3} ^{1 2 3 4} )\). Widzimy , że \(q(1)=2, \ q(2)=4, \ q(4)=3, \ q(3)=1\), a więc \(q\) jest cyklem, jest to permutacja nieparzysta. a także \(q^{-1}=( _{3 1 4 2} ^{1 2 3 4} )\) Inwersja zwie sie parę \((p(i), p(j))\) w sytuacji, gdy \(i< j\) i \(p(i) >p(j)\). Wracając do przykładu powyżej dla \(q\) łatwo widać, że istnieją trzy takie pary, tj \((2,1), \ (4,1), \ (4,3)\) Reguła: Jeśli \(p\) posiada nieparzystą liczbę inwersji, to jest permutacją nieparzystą. (tj. \(sgn(p)=-1\)). w przeciwnym razie jest ona permutacją parzystą, (tj. \(sgn(p)=1\)). Tw Cayleya Kazdą grupę rzędu \(n\) można zanurzyć w \(S_n\), tj każda grupa skończona jest izomorficzna z pewną podgrupą grupy permutacji. wzór na rozkład cyklu na transpozycje: \(s=(x_1....x_r) =(x_1 x_r) \circ ...\circ (x_1 x_2)\) Uwaga Oba Zapisy: \(p= ( _{b_2 b_3....b_1} ^{b_1 b_2 ... b_r} )\) i \(s=(b_1....b_r)\) znaczą to samo i uzywamy ich zamiennie. Przykład \(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 \(p \in S_n\) można przyporzadkować digraf \(D(p)= (X, A)\), gdzie X to wierzchołki (tj . elementy z \(S\)), zaś \(A=\{(i, \sigma(i)) : i \in X \}\) to zbiór łuków. Zbiór cykli digrafu \(D(p)\) zwie się kanonicznym rozkładem permutacji. I tak np dla permutacji \(T\) ma on postać \([3,6] [1,7,5,4] [2]\). Mówimy, że \(p \in S_n\) jest typu \(\lambda=<\lambda_1, ...\lambda_n>\), jesli w jej rozkładzie kanonicznym występuje \(\lambda_i\) cykli długości \(i\) dla \(i=1, ...,n\). Tu np . permutacja \(T\) jest typu \(\lambda=<1,1,0,1,0,0,0>\). Dla permutacji typu \(\lambda=<\lambda_1, ...\lambda_n>\) jest: \(\lambda_1+2\lambda_2+....+n\lambda_n=n\). zaś liczba wszystkich permutacji typu \(\lambda\) zbioru \(n\) elementowego jest równa: \(h(\lambda_1, ....\lambda_n)= \frac{n!}{1^{\lambda_1}....n^{\lambda_n} (\lambda_1)!....(\lambda_n)!}\) Liczba tych permutacji \(p\in S_n\), które w rozkładzie kanonicznym mają \(k\) cykli jest równa wartości bezwzględnej liczby \(s(n,k)\) tzw. liczby Stirlinga

ODPOWIEDZ