szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 19 sty 2008, o 04:19 
Użytkownik

Posty: 5840
Lokalizacja: Kraków
:arrow: 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, etc. El. neutralny e, to permutacja identycznościowa. itd. Warto zapamiętać te użyteczną formułke: :arrow: Permutacja 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 a t. że p(a)=a, tj p. 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łaczne, 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ą,




:!: :idea: :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 odwzor. 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 permutacją 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 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 p. nieparzystą. (tj. sgn(p)=-1). w przeciwnym razie jest ona p. 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:
:arrow: :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) :arrow:



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 p. 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= , jesli w jej rozkł. kanonicznym występuje \lambda_i cykli długości i dla i=1, ...,n. Tu np . permutacja T jest typu \lambda= . Dla p. typu \lambda= 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łądzie kanonicznym mają k cykli jest równa wartości bezwzględnej liczby s(n,k) :arrow: tzw. liczby Stirlinga

:arrow: :arrow:
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Czym są permutacje? - zadanie 2  mol_ksiazkowy  0
 permutacje zbioru  Minority  3
 Czym różni się objętośc od pojemności?  kejszi  1
 Permutacje liczb  herfoo  5
 permutacje- silnia  vital  9
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl