Algebra 0-12 permutacje.pdf

Wykład12

Permutacje

Niech X b¦dziezbiorem.Ka»d¡wzajemniejednoznaczn¡funkcj¦prze-

kształcaj¡c¡ X na X nazywamypermutacj¡zbioru X .Zbiórwszystkichper-

mutacjizbioru X oznaczamyprzez S ( X ).

Uwaga1 Permutacjamis¡wszystkiewzajemniejednoznaczneprzekształce-

niatoznaczyfunkcje,któres¡ró»nowarto±cioweis¡’na’.

Je±li X = { 1 , 2 ,...,n } tozamiast S ( X )b¦dziemypisa¢ S n .Wzbiorze

S n mo»nawprowadzi¢działanie składaniaprzekształce«.

Twierdzenie1 Struktura ( S n , ) jestgrup¡.Ponadto ¯ ¯ S n = n ! ije±lin> 2

toS n jestgrup¡nieabelow¡.

Dowód Działanieskładaniaprzekształce«jestł¡czne.Elementemneutral-

nymtegodziałaniajestfunkcjaidentyczno±ciowa i ( x )= x iponiewa»elemen-

tamizbioru S n s¡funkcjewzajemniejednoznacznetos¡tofunkcjeodwracalne.

Ka»d¡permutacj¦zezbioru S n mo»naprzedstawi¢wsposób”blokowy”,

tzn.je±li 2 S n to:

1 2 3 ... n

(1) (2) (3) ... ( n )

Przykład Elementamizbioru S 3 s¡nast¦puj¡cepermutacje:

123

132

123

321

i =

, 1 =

, 2 =

123

213

123

231

123

312

3 =

, 4 =

, 5 =

Zadanie Uło»y¢tabelk¦składaniapermutacjiwzbiorze S 3 .

Zadanie Wyznaczy¢ − 1 je±li:

123456

324516

Rozwi¡zanie Wystarczyzamieni¢wierszemiejscamiiuporz¡dkowa¢:

324516

123456

521346

− 1 =

Permutacj¦ 2 S n nazywamy cyklem je±liistniejepodzbiór { i 1 ,i 2 ,...,i k }2

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

i działato»samo±ciowonapozostałychelementachzbioru { 1 , 2 ,...,n } .

Przykład Permutacja:

123456

324516

jestcyklembonaszympodzbioremjest { 1 , 3 , 4 , 5 } .Apermutacja:

123456

364512

niejestcyklem.

Cykleb¦dziemyzapisywa¢wpostaci( i 1 ,i 2 ,...,i k ).Zatemwnaszym

przykładziepierwszapermutacjajestcyklem(1 , 3 , 4 , 5).Natomiastdruga

jestiloczynemcykli(1 , 3 , 4 , 5)(2 , 6).Dwacyklenazywamy rozłacznymi je±li

zbioryporuszanychprzeznieelementóws¡rozł¡czne.

Twierdzenie2 Ka»dapermutacjajestiloczynemcyklirozł¡cznych.

Zadanie Zapisa¢permutacj¦:

123456789

364512978

wpostaciiloczynucyklirozł¡cznych.

Rozwi¡zanie

123456789

364512978

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

Zadanie Zapisa¢wszystkiepermutacjezezbioru S 3 wpostaciiloczynucykli.

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»dycyklpostaci( i,j )nazywamy transpozycj¡ .

Twierdzenie3 Ka»d¡permutacj¦dosi¦zapisa¢wpostaciiloczynutrans-

pozycji.

i 1 ! i 2 ! ... ! i k ! i 1

Dowód Wystarczyudowodni¢,»edowolnycykljestiloczynemtranspozycji.

Rzeczywi±ciemamy:

( i 1 ,i 2 ,i 3 ,...,i k )=( i 1 ,i k )( i 1 ,i k − 1 ) ... ( i i ,i 2 )

Zadanie Zapisa¢permutacj¦:

123456789

364512978

jakoiloczyntranspozycji.

Rozwi¡zanie

123456789

364512978

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

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

Mówimy,»epermutacjajest parzysta je±lirozkładasi¦naparzyst¡ilo±¢

transpozycjii»ejest nieparzysta je±lirozkładasi¦nanieparzyst¡ilo±¢

transpozycji.

Uwaga2 Mo»naudowodni¢,»ezbiorypermutacjiparzystychinieparzystych

s¡rozł¡czne.

Zadanie Czypermutacja:

123456789

364512978

jestparzysta?

Rozwi¡zanie Permutacjatajestparzystaboudowodnili±mywcze±niej,»e

rozkładasi¦nasze±¢(czyliparzyst¡ilo±¢)transpozycji.

Oznaczmyprzez A n zbiórwszystkichpermutacjiparzystych.Wtedydzia-

łanie jestdobrzeokre±lonewzbiorze A n imamy:

Twierdzenie4 Struktura ( A n , ) jestgrup¡.Ponadto ¯ ¯ A n = n ! 2 .

Innysposóbbadania,czypermutacjajestparzysta.

Je±li 2 S n tomówimy,»edla i<j zachodzi inwersja je±li ( i ) > ( j ).

Twierdzenie5 Permutacjajestparzystawtedyitylkowtedygdymapa-

rzyst¡ilo±¢inwersji.

Zadanie Ileinwersjimapermutacja:

123456789

365214978

Rozwi¡zanie Permutacjatama10inwersji(awi¦cjestpermutacj¡parzy-

st¡).

Niech 2 S n mówimy,»eliczbanaturalna k ,jest rz¦dem permutacji

je±li k = i , k 6 =0orazje±li l = i to k ¬ l .

Twierdzenie6 Rz¦demcyklujestjegodługo±¢.Je±lipermutacjajestiloczy-

nemcyklirozł¡cznychtojejrz¦demjestnajmniejszawspólnawielokrotno±¢

długo±cicykliwchodz¡cychwjejzapis.

Przykład Rz¦dempermutacji(1 , 3 , 5 , 4 , 6)jest5,arz¦dempermutacji

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

jestNWW(4 , 6)=12.

Zadanie Obliczy¢[(2 , 3 , 4 , 5)(1 , 6)] 12345 .

Rozwi¡zanie Permutacja(2 , 3 , 4 , 5)(1 , 6)marz¡d4.Zatem

[(2 , 3 , 4 , 5)(1 , 6)] 4 k = i k = i.

Trzebawi¦cpodzieli¢liczb¦12345przez4zreszt¡.Mamy12345=4 · 3086+1

tooznacza,»e:

[(2 , 3 , 4 , 5)(1 , 6)] 12345 =[(2 , 3 , 4 , 5)(1 , 6)] 4 · 3086+1 =

([(2 , 3 , 4 , 5)(1 , 6)] 4 ) 3086 [(2 , 3 , 4 , 5)(1 , 6)] 1 =(2 , 3 , 4 , 5)(1 , 6) .

Zadanie Rozwi¡za¢równanie:

185 243 x 125 277 = 49 76 ,

gdzie =(1 , 2 , 3 , 4) , =(1 , 2)(3 , 4 , 5),a x jestniewiadom¡.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: