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)