Permutacje 1 - algebra

Nasza ocena:

3
Pobrań: 28
Wyświetleń: 770
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Permutacje 1 - algebra - strona 1 Permutacje 1 - algebra - strona 2 Permutacje 1 - algebra - strona 3

Fragment notatki:


Wykład 12 Permutacje Niech  X  będzie zbiorem. Każdą wzajemnie jednoznaczną funkcję prze- kształcającą  X  na  X  nazywamy permutacją zbioru  X . Zbiór wszystkich per- mutacji zbioru  X  oznaczamy przez  S ( X ). Uwaga 1  Permutacjami są wszystkie wzajemnie jednoznaczne przekształce- nia to znaczy funkcje, które są różnowartościowe i są ’na’. Jeśli  X  =  { 1 ,  2 , . . . , n}  to zamiast  S ( X ) będziemy pisać  Sn . W zbiorze Sn  można wprowadzić działanie  ◦  składania przekształceń. Twierdzenie 1  Struktura  ( Sn, ◦ )  jest grupą. Ponadto  ¯ Sn  =  n !  i jeśli n   2 to Sn jest grupą nieabelową. Dowód  Działanie składania przekształceń jest łączne. Elementem neutral- nym tego działania jest funkcja identycznościowa  i ( x ) =  x  i ponieważ elemen- tami zbioru  Sn  są funkcje wzajemnie jednoznaczne to są to funkcje odwracalne. Każdą permutację ze zbioru  Sn  można przedstawić w sposób ”blokowy”, tzn. jeśli  σ ∈ Sn  to: σ  = 1 2 3 . . . n σ (1)  σ (2)  σ (3)  . . . σ ( n ) Przykład  Elementami zbioru  S 3 są następujące permutacje: i  = 1 2 3 1 2 3 , σ 1 = 1 2 3 1 3 2 , σ 2 = 1 2 3 3 2 1 , σ 3 = 1 2 3 2 1 3 , σ 4 = 1 2 3 2 3 1 , σ 5 = 1 2 3 3 1 2 Zadanie  Ułożyć tabelkę składania permutacji w zbiorze  S 3. Zadanie  Wyznaczyć  σ− 1 jeśli: σ  = 1 2 3 4 5 6 3 2 4 5 1 6 Rozwiązanie  Wystarczy zamienić wiersze miejscami i uporządkować: σ − 1 = 3 2 4 5 1 6 1 2 3 4 5 6 = 1 2 3 4 5 6 5 2 1 3 4 6 1 Permutację  τ ∈ Sn  nazywamy  cyklem  jeśli istnieje podzbiór  {i 1 , i 2 , . . . , ik} ∈ { 1 ,  2 , . . . , n} , że i 1 τ → i 2 τ → . . . τ → ik τ → i 1 i  τ  działa tożsamościowo na pozostałych elementach zbioru  { 1 ,  2 , . . . , n} . Przykład  Permutacja: 1 2 3 4 5 6 3 2 4 5 1 6 jest cyklem bo naszym podzbiorem jest  { 1 ,  3 ,  4 ,  5 } . A permutacja: 1 2 3 4 5 6 3 6 4 5 1 2 nie jest cyklem. Cykle będziemy zapisywać w postaci ( i 1 , i 2 , . . . , ik ). Zatem w naszym przykładzie pierwsza permutacja jest cyklem (1 ,  3 ,  4 ,  5). Natomiast druga jest iloczynem cykli (1 ,  3 ,  4 ,  5)(2 ,  6). Dwa cykle nazywamy  rozłacznymi  jeśli zbiory poruszanych przez nie elementów są rozłączne. Twierdzenie 2  Każda permutacja jest iloczynem cykli rozłącznych. Zadanie  Zapisać permutację: 1 2 3 4 5 6 7 8 9 3 6 4 5 1 2 9 7 8 w postaci iloczynu cykli rozłącznych. Rozwiązanie 1 2 3 4 5 6 7 8 9 3 6 4 5 1 2 9 7 8

(…)

…, czy permutacja jest parzysta.
Jeśli σ ∈ Sn to mówimy, że dla i < j zachodzi inwersja jeśli σ(i) > σ(j).
Twierdzenie 5 Permutacja σ jest parzysta wtedy i tylko wtedy gdy ma parzystą ilość inwersji.
3
Zadanie Ile inwersji ma permutacja:
1 2 3 4 5 6 7 8 9
3 6 5 2 1 4 9 7 8
?
Rozwiązanie Permutacja ta ma 10 inwersji (a więc jest permutacją parzystą).
Niech σ ∈ Sn mówimy, że liczba naturalna k, jest rzędem permutacji σ
jeśli σ k = i, k = 0 oraz jeśli σ l = i to k l.
Twierdzenie 6 Rzędem cyklu jest jego długość. Jeśli permutacja jest iloczynem cykli rozłącznych to jej rzędem jest najmniejsza wspólna wielokrotność
długości cykli wchodzących w jej zapis.
Przykład Rzędem permutacji (1, 3, 5, 4, 6) jest 5, a rzędem permutacji
(1, 3, 4, 5)(2, 6, 7, 8, 9, 10)
jest NWW(4, 6) = 12.
Zadanie Obliczyć [(2, 3, 4, 5)(1, 6…

Sn można wprowadzić działanie ◦ składania przekształceń.
¯
Twierdzenie 1 Struktura (Sn , ◦) jest grupą. Ponadto Sn = n! i jeśli n > 2
to Sn jest grupą nieabelową.
Dowód Działanie składania przekształceń jest łączne. Elementem neutralnym tego działania jest funkcja identycznościowa i(x) = x i ponieważ elementami zbioru Sn są funkcje wzajemnie jednoznaczne to są to funkcje odwracalne.
Każdą permutację…
... zobacz całą notatkę

Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz