Algebra 0-12 permutacje

[ Pobierz całość w formacie 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
123
!
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
!
123456
521346
!
−
1
=
=
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.
2
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.
3
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¡.
4
[ Pobierz całość w formacie PDF ]