3582320541

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 per-mutacji zbioru X oznaczamy przez S(X).

Uwaga 1 Permutacjami są wszystkie wzajemnie jednoznaczne przekształcenia to znaczy funkcje, które są różnowartosciowe i są ’na’.

Jeśli X = {1,2,..., n} to zamiast S(X) będziemy pisać S_n. W zbiorze S_n można wprowadzić działanie o składania przekształceń.

Twierdzenie 1 Struktura (S_n, o) jest grupą. Ponadto S_n — n! i jeśli n > 2 to S_n 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 S_n są funkcje wzajemnie jednoznaczne to są to funkcje odwracalne.* Każdą peimutację ze zbioru S_n można przedstawić w sposób "blokowy”, tzn. jeśli a € S_n to:

( 1    2    3

^ cr(l) <r(2) cr(3)

n

a(n)

)

Przykład Elementami zbioru S$ są następujące permutacje:

. _ f 1 2 3 N    _ f 1 2 3\    _ ( 1 2 Z\

^{^}    (123]’    ^ai    l 1    3 2 J ’    ^a2    i 3 2 1 J ’

ó 1 2 3 \    _ / 1 2 3 \    _ f 1 2 3 \

⁰³    ^2 1 3 y ’    ⁰⁴    ^ 2    3 1 J ’    ⁰⁵    ^ 3 1 2 J

Zadanie Ułożyć tabelkę składania permutacji w zbiorze S₃. Zadanie Wyznaczyć er^-1 jeśli:

/ 1 2 3 4 5 6 \ [3245isj

Rozwiązanie Wystarczy zamienić wiersze miejscami i uporządkować:

-i_f ³ 2 4 5 1 0 \_/l 2 3 4 5 6 \

⁰ —\^1 2 3 4 5 6 y \ 5 2 1 3 4 6 y

1