Wykład 12
Permutacje
Niech X będzie zbiorem. Każdą wzajemnie jednoznaczną funkcję przekształcającą X na X nazywamy permutacją zbioru X. Zbiór wszystkich permutacji zbioru X oznaczamy przez S(X).
Uwaga 1 Permutacjami są wszystkie wzajemnie jednoznaczne przekształcenia 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 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ę 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 S3 są następujące permutacje:
i=
σ3 =
1
1
1
2
2
2
2
1
3
, σ1 =
3
3
, σ4 =
3
1
1
1
2
2
3
2
3
3
2
3
1
, σ2 =
,
σ5 =
1
3
1
3
2
2
2
1
3
1
3
2
,
Zadanie Ułożyć tabelkę składania permutacji w zbiorze S3 .
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
1 2 3 4 5 6
5 2 1 3 4 6
Permutację τ ∈ Sn nazywamy cyklem jeśli istnieje podzbiór {i1 , i2 , . . . , ik } ∈
{1, 2, . . . , n}, że
τ
τ
τ
τ
i 1 → i2 → . . . → i k → i1
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 (i1 , i2 , . . . , 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
= (1, 3, 4, 5)(2, 6)(7, 9, 8)
Zadanie Zapisać wszystkie permutacje ze zbioru S3 w postaci iloczynu cykli.
Zadanie Wymnożyć permutacje [(1, 2, 3, 4)(7, 8)][(1, 2, 3, 5, 6)(4, 7)]
Rozwiązanie
[(1, 2, 3, 4)(7, 8)][(1, 2, 3, 5, 6)(4, 7)] = (1, 3, 5, 6, 2, 4, 8, 7).
Każdy cykl postaci (i, j) nazywamy transpozycją.
Twierdzenie 3 Każdą permutację do się zapisać w postaci iloczynu transpozycji.
2
Dowód Wystarczy udowodnić, że dowolny cykl jest iloczynem transpozycji.
Rzeczywiście mamy:
(i1 , i2 , i3 , . . . , ik ) = (i1 , ik )(i1 , ik−1 ) . . . (ii , i2 )
Zadanie Zapisać permutację:
1 2 3 4 5 6 7 8 9
3 6 4 5 1 2 9 7 8
jako iloczyn transpozycji.
Rozwiązanie
1 2 3 4 5 6 7 8 9
= (1, 3, 4, 5)(2, 6)(7, 9, 8)
3 6 4 5 1 2 9 7 8
(1, 3, 4, 5)(2, 6)(7, 9, 8) = (1, 5)(1, 4)(1, 3)(2, 6)(7,
(…)
…, 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…
... zobacz całą notatkę
Komentarze użytkowników (0)