szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 6 maja 2009, o 22:10 
Użytkownik

Posty: 5821
Lokalizacja: Kraków
:arrow: 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ć :arrow: (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łę: :arrow: 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\}. :arrow: Permutację p \in S_n zapisuje się zwykle w postaci:
:arrow:
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. :arrow: 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.
:arrow: Def Permutację p t. że, nie ma ona punktów stałych -tj takich j że p(j)=j zwiemy nieporządkiem,
:arrow: Powiemy, że p i qrozłączne, jeśli warunek p(j)= j pociąga q(j) \neq j. :arrow: 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:
:arrow: 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} )
:arrow: 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ą,




:arrow: 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ą.


:arrow: 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} )



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



:arrow: 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.


:arrow: 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:
:arrow: 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) :arrow: tzw. liczby Stirlinga
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Czym są permutacje?  mol_ksiazkowy  0
 Czym "zajmują" się elementy Euklidesa ?  kuba1989  5
 permutacje ,rozwiąż równanie  rafalek  1
 losowe permutacje  Rafix_  10
 Czym różni się zbieżność warunkowa od bezwzględnej ?  KiiiX  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl