24421

24421



Permutację r 6 Sn 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,*2,... ,*'*). 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



Wyszukiwarka

Podobne podstrony:
Image1890 Jeśli istnieje e takie.że 0.(x0je)cC
Image2217 Jeśli istnieje e takie, że 0(x0je)c £}, to lim f(x)=f(x$). x^x0
Image2218 Jeśli istnieje e takie,że 0+ (x0je)cCj, to lim f(x) =f(x^). x^x0+
bhp (14) Jeśli istnieje prawdopodobieństwo, że niebezpieczne środki chemiczne przenikną do Twojego d
bhp (25) Jeśli istnieje prawdopodobieństwo, że niebezpieczne środki chemiczne przenikną do Twojego d
img027 (65) I Levi-Strauss Wydaje się, że sam Levi-Strauss skłonny jest sądzić, że jeśli istnieją ja
img058 58 Oeflnic^i^S.a. Mówley, źe funkcja f Jaat różniczkowaIna ar punkcie a, jeśli istnieje funkc
O języku A C E* powiemy, że jest jednostajnie konfluentny, jeśli istnieje taka stała c G N, że: /w,v
skanuj0003 bmp Ze pospólstwo i chłopstwo chujem to nazywa. Przy tym istnieją inne najrozmaitsze słow
13 0.3. CIĄGI LICZBOWE a więc ostatecznie dla każdego e > O istnieje no G N że jeśli n> no to
jeśli istnieje obliczenie sosi • • • Sm+l maszyny A na słowie u takie, że sm+i G F. Oto przykłady

więcej podobnych podstron