Permutacje dz f

1
Działania na permutacjach.
W tym celu permutację zapisujemy w postaci
1 2 ... n
�ł �ł
�ł
f =
�ła a2 ... an �ł
�ł
�ł 1 łł
albo f ( i ) = ai i= 1, 2, ... , n
- element stojący na miejscu i przenieś na miejsce ai .
Zbiór permutacji n- elementowych oznaczymy symbolem Sn.
Składanie permutacji.
Składanie permutacji wykonuje się podobnie jak składanie innych
funkcji. Niech będą dane dwie permutacje
1 2 3 4 5
1 2 3 4 5 �ł �ł
�ł �ł
g = �ł �ł
f = �ł �ł
�ł2 5 1 4 3�ł
�ł3 4 1 5 2�ł
�ł łł �ł łł
Złożeniem permutacji f i g jest permutacja f g = ( f ( g))
1 2 3 4 5
�ł �ł
fg = �ł �ł
�ł4 2 3 5 1�ł
�ł łł
Istotna jest kolejność operacji. W wyniku złozenia gf = g( f )
otrzymujemy
1 2 3 4 5
�ł �ł
gf = �ł �ł
�ł1 4 2 3 5�ł
�ł łł
Składanie permutacji jest na ogół nieprzemienne. Natomiast jest
działaniem łącznym
f ( g ( h )) = (f g) h = f (g h) .
Permutacja identycznościowa.
Permutację identycznościową oznaczymy literą e. Jest to permutacja
dz na permutacjach
1
2
1 2 3 ... n
�ł �ł
e = �ł �ł
�ł1 2 3 ... n�ł lub inaczej e( i ) = i i = 1,2, ..., n
�ł łł
Dla każdej permutacji f " Sn zachodzi f e = e f = f
Permutacja odwrotna.
Permutacją odwrotną do danej permutacji f jest permutacja, dla której
f -1 f = e.
Jeżeli f ( i ) = j , to f -1( j ) = i .
Przykład.
Wyznaczyć permutację odwrotną do permutacji
1 2 3 4 5
�ł �ł
1 2 3 4 5
�ł �ł
g = �ł �ł
f = �ł �ł
a) b) �ł2 5 1 4 3�ł
�ł3 4 1 5 2�ł
�ł łł �ł łł
Korzystamy z własności: jeżeli f ( i ) = j , to f -1( j ) = i .
Permutację odwrotna do f otrzymujemy zamieniając wiersz górny z
dolnym, po czym, dla uzyskania bardziej przejrzystej tablicy
sortujemy ją w/g elementów górnego wiersza
3 4 1 5 2 1 2 3 4 5
�ł �ł �ł �ł
f-1 = �ł �ł �ł
�ł1 2 3 4 5�ł = �ł
�ł3 5 1 2 4�ł
�ł łł �ł łł
Można sprawdzić, że f -1 f = e . Istotnie,
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
�ł �ł�ł �ł �ł �ł
f f-1 = �ł �ł�ł �ł �ł
�ł3 5 1 2 4�ł�ł3 4 1 5 2�ł = �ł
�ł1 2 3 4 5�ł = e
�ł łł�ł łł �ł łł
A także
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
�ł �ł �ł �ł �ł �ł
-1
f f = �ł �ł �ł �ł
�ł3 4 1 5 2�ł �ł �ł1 2 3 4 5�ł = e
�ł3 5 1 2 4�ł = �ł
�ł łł �ł łł �ł łł
dz na permutacjach
2
3
Podobnie dla permutacji g
2 5 1 4 3 1 2 3 4 5
�ł �ł �ł �ł
g-1 = �ł �ł �ł
�ł1 2 3 4 5�ł = �ł
�ł3 1 5 4 2�ł
�ł łł �ł łł
oraz
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
�ł �ł�ł �ł �ł �ł
g-1g = �ł �ł�ł �ł �ł
�ł3 1 5 4 2�ł�ł2 5 1 4 3�ł = �ł
�ł1 2 3 4 5�ł = e
�ł łł�ł łł �ł łł
Jak łatwo można sprawdzić, także g g -1 = e.
Transpozycja
Jest to permutacja, która zamienia miejscami tylko dwa elementy, a
pozostałe zostawia bez zmian.
Przykłady transpozycji
1 2 3 4 5
�ł �ł
1 2 3 4 5 6
�ł �ł
q = �ł �ł
p = �ł �ł
�ł4 2 3 1 5�ł
�ł1 5 3 4 2 6�ł
�ł łł
�ł łł
Permutację można przedstawić jako złożenie transpozycji przy czym
rozkład ten nie jest jednoznaczny. Przykład takiego rozkładu:
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
�ł �ł �ł �ł�ł �ł�ł �ł
f = �ł �ł �ł�ł �ł�ł �ł
�ł3 4 1 5 2�ł = �ł
�ł3 2 1 4 5�ł�ł1 4 3 2 5�ł�ł1 2 3 5 4�ł
�ł łł �ł łł�ł łł�ł łł
Rozkład permutacji na transpozycje nie jest jednoznaczny, ale
niezmiennicza jest parzystość liczby transpozycji. Dlatego mówimy o
permutacjach parzystych bądz nieparzystych.
Każda transpozycja zmienia liczbę inwersji (nieporządków) o liczbę
nieparzystą.
Inwersją jest liczba tych elementów ciągu (a1, a2, .. , ak} dla których
a j > a k przy j < k.
dz na permutacjach
3
4
Cykle
Cyklem nazywamy permutacje postaci
a1 a2 ... ak-1 ak ak+1 ... an-1 an
�ł �ł
�ł
f =
�ła a3 ... ak a1 ak+1 ... an-1 an �ł
�ł
�ł 2 łł
Zwykle przy zapisie opuszczamy część tablicy która nie wnosi zmian
i operując na cyklach zapisujemy krócej
a1 a2 ... ak-1 ak
�ł �ł
�ł
f =
�ła a3 ... ak a1 �ł
�ł
�ł 2 łł
Często jest stosowany jeszcze krótszy zapis cyklu
a1 a2 ... ak-1 ak
�ł �ł
�ł
f =
�ła a3 ... ak a1 �ł =(a1,a2,...,an)
�ł
�ł 2 łł
Dowodzi się, że każdą permutację można przedstawić jako złożenie
pewnej liczby cykli.
Przykład rozkładu na cykle
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
�ł �ł �ł �ł�ł �ł�ł �ł
g = �ł �ł �ł�ł �ł�ł �ł
�ł2 1 5 3 6 4�ł = �ł
�ł3 2 5 4 1 6�ł�ł2 4 3 1 5 6�ł�ł1 5 3 4 6 2�ł
�ł łł �ł łł�ł łł�ł łł
lub krócej
1 2 3 4 5 6 1 3 5 1 2 4 2 5 6
�ł �ł �ł �ł�ł �ł�ł �ł
g = �ł �ł �ł�ł �ł�ł �ł
�ł2 1 5 3 6 4�ł = �ł
�ł3 5 1�ł�ł2 4 1�ł�ł5 6 2�ł
�ł łł �ł łł�ł łł�ł łł
albo jeszcze krócej
g=(1 3 5)(1 2 4)(2 5 6)
dz na permutacjach
4

Wyszukiwarka

Podobne podstrony:
Rodzaj i zakres … Dz U 1995 25
Dz U 2002 199 1671 o przewozie drogowym towarów niebezpiecznych
Dz U 2003 190 1864 zmiana z dnia 2003 09 12
Dz U 00 40 470 bezpieczeństwo i higiena pracy przy pracach spawalniczych
dz u nr54 5 12 97
Dz U 2006 Nr49 poz356
Dz U 04 nr257 poz2573
Dz U 03 61 552 sposób oznakowania miejsc służących do przechowywania lub zawierających substancj
Dz Urz Min Fin z dnia 10 września 2014 r poz

więcej podobnych podstron