24421

Permutację r 6 S_n nazywamy cyklem jeśli istnieje podzbiór {*i, *2.....**} G

{1,2,... ,n}, że

. r . r    r . r .

i r działa tożsamościowo na pozostałych elementach zbioru {1,2,... ,n}. Przykład Permutacja:

/ 1    2    3    4    5    G\

^ 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    C    4    5    1    2    )

nie jest cyklem.

Cykle będziemy zapisywać w postaci (»i,*₂,... ,*'*). 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łącznymi jeśli zbiory poruszanych przez nie elementów są rozłączne.

Twierdzenie 2 Każda permutacja jest iloczynem cykli rozłącznych.

Zadanie Zapisać permutację:

(l 2    3    4    5    G    7    8

\3 6    4    5    1    2    9    7    8/

w postaci iloczynu cykli rozłącznych. Rozwiązanie

(1,3,4,5)(2,6)(7,9,8)

/ 1    2    3    4 5 6    7    8 9 \

\ 3    6    4    5 1 2    9    7 8 j

Zadanie Zapisać wszystkie permutacje ze zbioru S% w postaci iloczynu cykli. Zadćuiic 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.

9