Permutációk véges halmazon (el®adásvázlat, 2008. február 12.) Maróti Miklós
Ennek az el®adásnak a megértéséhez a következ® fogalmakat kell tudni: ismétlés nélküli variáció, leképezés, indulási és érkezési halmaz, szürjektív, injektív, bijektív és identikus leképezés, leképezések szorzata és inverze, csoport, Abel-csoport, asszociatív, illetve kommutatív m¶velet, egységelem, csoportelem inverze és hatványa, determináns és tulajdonságai. Az el®adáshoz ajánlott jegyzet:
• •
Klasszikus és lineáris algebra, Polygon Kiadó, Szeged, 1999. Szendrei Ágnes: Diszkrét matematika, Polygon Kiadó, Szeged, 19942002. Klukovits Lajos:
1. De níció. Tetsz®leges
Az
A
halmaz permutációin a
n
pozitív egészre az
A
π ∈ Sn
{1, . . . , n}
π : A → A
bijektív leképezéseket értjünk.
halmaz összes permutációinak halmazát
Sn -nel
jelöljük.
2. Jelölés.
permutációt megadhatjuk kétsoros írásmóddal
π=
1 2 ··· 1π 2π · · ·
n , nπ
vagy elempárok halmazaként:
π = {(1, 1π), (2, 2π), . . . , (n, nπ)}.
3. Példa.
Ha
α ∈ S3
az a permutáció, amelyre
α=
4. Példa.
1 2 3 2 1 3
1α = 2, 2α = 1
és
3α = 3,
akkor
= {(1, 2), (2, 1), (3, 3)}.
Nem minden leképezés permutáció, például a
ϕ=
1 2 3 3 1 3
leképezés se nem injektív (mert az az érkezési halmaz
2
= {(1, 3), (2, 1), (3, 3)}
1 és 3 elemeknek ugyanaz a képe) se nem szürjektív (mert
elmének nincsen ®se).
5. Tétel. |Sn | = n! 6. Példa. 1 S1 = , 1 1 2 1 2 S2 = , , 1 2 2 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 S3 = , , , , , . 1 2 3 2 1 3 3 2 1 1 3 2 2 3 1 3 1 2
7. Tétel. (Sn ; ◦) 8. Példa.
csoport.
Számoljuk ki az
1 2 3 α= 2 1 3
és
β=
1 2 3 2 3 1
permutációk szorzatát.
Tudjuk, hogy minden
x
elemre
x(αβ) = (xα)β
(ez a leképezés
szorzás de níciója). Tehát
1(αβ) = (1α)β = 2β = 3, 2(αβ) = (2α)β = 1β = 2, 3(αβ) = (3α)β = 3β = 1, azaz
1 2 3 αβ = . 3 2 1
Most kiszámoljuk a
βα
szorzatot is (a zárójelek elhagyásával):
1βα = 2α = 1, 2βα = 3α = 3, 3βα = 1α = 2, azaz
βα = Vegyük észre, hogy kiszámoljuk
β
αβ 6= βα,
azaz a permutációk szorzása nem kommutatív.
β= ezért
1 2 3 2 3 1
= {(1, 2), (2, 3), (3, 1)}
1 2 3 = {(2, 1), (3, 2), (1, 3)} = {(1, 3), (2, 1), (3, 2)} = . 3 1 2
−1
β
Természetesen
és
β −1
szorzata az identikus leképezés:
ββ −1 = β −1 β =
9. De níció.
Végezetül
inverzét. Mivel
β
1 2 3 . 1 3 2
A
1 2 3 . 1 2 3
π ∈ Sn permutáció az x ∈ {1, . . . , n} elemet mozgatja, ha xπ 6= x. Mπ -vel jelöljük, azaz
A
π ∈ Sn
által mozgatott elemek halmazát
Mπ = { x ∈ {1, . . . , n} : xπ 6= x }.
10. Példa.
Az
permutáció által mozgatott elemek
1 2 3 α= 2 1 3 halmaza Mα = {1, 2}.
11. Kérdések.
permutáció van, amelyre
(1) (2) (3) (4)
Hány olyan
π ∈ S9
Mπ = {2, 3, 5}, |Mπ | = 1, |Mπ | = 2, |Mπ | = 3?
12. De níció.
A
π, σ ∈ Sn
permutációkat idegennek nevezzük, ha
Mπ ∩ Mσ = ∅ .
13. Kérdések. (1) (2) (3)
Az
Sn
halmazon az idegenség reláció re exív, szimmetrikus, illetve tranzitív-e?
Hány olyan permutációja van
S4 -nek,
amely az
1234 2134
Van-e olyan permutáció, amely idegen az inverzével?
14. Tétel.
Ha a π, σ ∈ Sn permutációk idegenek, akkor (1) πσ = σπ , és (2) (πσ)k = π k σ k minden k egészre. 2
permutációval idegen?
15. De níció.
n ≥ k ≥ 2, és az a1 , . . . , ak ∈ {1, . . . , n} π ∈ Sn permutációt, amelyre
Legyen
z®ek. Ekkor azt a
elemek páronként különbö-
a1 π = a2 , a2 π = a3 , . . .
ak−1 π = ak , ak π = a1 , és
xπ = x
x ∈ {1, . . . , n} \ {a1 , . . . , ak }
minden
elemre, ciklusnak nevezzük és röviden így
jelöljük:
A
k
számot a ciklus hosszának
π = (a1 a2 · · · ak ). nevezzük. A 2 hosszúságú
ciklusokat transzpozícióknak
hívjuk.
16. Példa.
Az
1 2 3 α= 2 1 3 permutáció ciklus, mivel a k = 2, a1 = 1 és a2 = 2 választással éppen ezt kapjuk, azaz α = (1 2). Mivel α hossza éppen 2, ezért α transzpozíció is. A 1 2 3 β= 2 3 1 permutáció szintén ciklus, és
a permutációt
β = (1 2 3).
17. Kérdések. (1) (2)
Mi az
(a1 a2 · · · ak ) ciklus által mozgatott elemek halmaza? π, σ, τ ∈ S7 páronként idegen permutációk, akkor (πστ )5 = π 5 σ 5 τ 5 ?
Igaz-e, hogy ha
18. Megjegyzés.
Vegyük észre, hogy egy permutáció ciklusos alakban való megadása nem
egyértelm¶! Egyrészt ugyanazt a permutációt többféleképpen is felírhatjuk ciklusként:
(1 2 3) = (2 3 1) = (3 1 2). A másik probléma pedig az, hogy az
S3
vagy esetleg az
S4
akkor
viszont
(1 2 3)
permutációról nem tudjuk eldönteni, hogy az
csoport eleme-e. Természetesen ha
S3 -beli
permutációkról beszélünk,
1 2 3 (1 2 3) = , 2 3 1 S4 -ben
már
1 2 3 4 (1 2 3) = , 2 3 1 4
és ez a két permutáció nem ugyanaz. Ugyan ez a probléma az identikus permutáció id jelölésével is, arról sem lehet eldönteni, hogy melyik permutációcsoportban használjuk.
19. Példa. S1 = {id}, S2 = {id, (1 2)}, S3 = {id, (1 2), (1 3), (2 3), (1 2 3), (3 2 1)}.
20. Kérdések. (1) (2) (3) (4)
S4 -ben? S4 -ben? ciklus van S4 -ben? ciklus van S4 -ben?
Hány transzpozíció van
Hány 3-hosszúságú ciklus van Hány 4-hosszúságú Hány 1-hosszúságú
3
(5) (6) (7)
Hány ciklus van
S4 -ben?
Hány olyan permutáció van Hány
21. Példa.
n-hosszúságú
S4 -ben amely Sn -ben?
nem ciklus?
ciklus van
Természetesen nem minden permutáció ciklus, vegyük például a
π=
1 2 3 4 5 2 3 1 5 4
π ciklus, és tekintsük azt az esetet, amikor a1 = 1. Ekkor a1 π = 2, azaz a2 = 2, továbbá a2 π = 3, azaz a3 = 3. A következ® lépésben azt kapjuk, hogy a3 π = 1 ami éppen egyenl® a1 -gyel, azaz k = 3 és az (1 2 3) ciklust kaptuk. Viszont π több elemet mozgat mint 3, tehát π nem egyenl® (1 2 3)-mal, azaz a1 6= 1. Minden más permutációt. Tegyük fel, hogy
esetben hasonló ellentmondásra jutunk. Persze
π
el®áll ciklusok szorzataként:
π = (1 2 3)(4 5).
22. Tétel. Minden Sn -beli permutáció el®áll páronként idegen ciklusok szorzataként, és ez az el®állítás a tényez®k sorrendjét®l eltekintve egyértelm¶en meghatározott. (Az identikus permutációt ciklusok üres szorzatának tekintjük.) 23. Példa.
Adjuk meg a
szorzataként.
π = (5 2 3 4)(1 3 5)(4 3 7)
permutációt páronként idegen ciklusok
Tekintsük azokat az elemeket, melyeket a szorzat valamely tagja mozgat:
{1, 2, 3, 4, 5, 7}. a π permutáció
Vegyünk ki ezek közül egyet, mondjuk az
1-gyet,
és számoljuk ki, hogy ezt
milyen elemekbe viszi át:
1π = 1(5 2 3 4)(1 3 5)(4 3 7) = 1(1 3 5)(4 3 7) = 3(4 3 7) = 7. Folytassuk a kapott elemekkel, azaz
7π = 7(5 2 3 4)(1 3 5)(4 3 7) = 7(1 3 5)(4 3 7) = 7(4 3 7) = 4, 4π = 4(5 2 3 4)(1 3 5)(4 3 7) = 5(1 3 5)(4 3 7) = 1(4 3 7) = 1. Visszaértünk ahhoz az elemhez, amib®l kiindultunk, tehát megvan az els® ciklusunk: A maradék elemekb®l vegyük a következ®t, mondjuk a
2-t®t,
(1 7 4). π
és számoljuk ki hogy ezt
milyen elemekbe viszi át:
2π = 2(5 2 3 4)(1 3 5)(4 3 7) = 3(1 3 5)(4 3 7) = 5(4 3 7) = 5, 5π = 5(5 2 3 4)(1 3 5)(4 3 7) = 2(1 3 5)(4 3 7) = 2(4 3 7) = 2, azaz a második ciklus a
(2 5)
transzpozíció. Kimaradt még a
3,
amelyre elvégezve a számo-
lást azt kapjuk, hogy
3π = 3(5 2 3 4)(1 3 5)(4 3 7) = 4(1 3 5)(4 3 7) = 4(4 3 7) = 3, azaz
π
a
3-mat
nem mozgatja, tehát ezt az elemet gyelmen kívül hagyhatjuk.
páronként idegen ciklusok szorzatára bontott alakja
π = (1 7 4)(2 5).
Tehát
π
Ezt a számolást nem
írjuk le általában, hanem fejben végezzük el!
24. Kérdések.
Hány olyan permutáció van
G-ben,
amelynek páronként idegen ciklusok
P alakú: P = (· ·)(· ·), P = (· ·)(· ·), P = (· ·)(· · ·)?
szorzatára bontott alakja
(1) G = S4 , (2) G = S5 , (3) G = S5 ,
25. Tétel.
Tetsz®leges
π = (a1 a2 · · · ak ) ∈ Sn ciklusra (1) = (ak ak−1 · · · a1 ), k (2) π = id, (3) Ha i ≡ j (mod k), akkor π i = π j . π −1
4
26. Példa.
((1 2 3 4)(5 6 7)(8 9))−22 permutációt páronként idegen ciklusok (1 2 3 4), (5 6 7) és (8 9) ciklusok páronként idegenek, ezért
Kiszámoljuk az
szorzataként. Mivel az
((1 2 3 4)(5 6 7)(8 9))−22 = (1 2 3 4)−22 (5 6 7)−22 (8 9)−22 . Az
(1 2 3 4)
ciklus hossza
4
−22-edik
és a
hatványát keressük. Mivel
−22 ≡ 2 (mod 4),
ezért
Hasonlóan
(1 2 3 4)−22 = (1 2 3 4)2 = (1 3)(2 4). −22 ≡ −1 (mod 3), illetve −22 ≡ 0 (mod 2), azaz (5 6 7)−22 = (5 6 7)−1 = (7 6 5), −22
(8 9)
és
0
= (8 9) = id.
Tehát
((1 2 3 4)(5 6 7))−22 = (1 3)(2 4)(7 6 5).
27. Példa.
Oldjuk meg az
(1 3 2)(2 5)π(4 5 7) = (2 6) egyenletet. Az egyenlet mindkét oldalát ugyanazzal a permutációval ugyanarról az oldalról beszorozhatjuk. El®ször balról szorzunk
(1 3 2)
−1
(1 3 2)
inverzével:
(1 3 2)(2 5)π(4 5 7) = (1 3 2)−1 (2 6),
azaz
(2 5)π(4 5 7) = (2 3 1)(2 6). Ezt folytatva azt kapjuk, hogy
π = (5 2)(2 3 1)(2 6)(7 5 4), amit a szokásos módon páronként idegen ciklusok szorzatára bontunk:
28. Tétel.
π = (5 3 1 6 2 4 7).
Tetsz®leges ciklus felírható transzpozíciók szorzataként, mégpedig
(a1 a2 a3 · · · ak ) = (a1 a2 )(a1 a3 ) · · · (a1 ak ). Következésképpen, minden permutáció transzpozíciók szorzatára bontható (de ez általában nem egyértelm¶).
29. Példa. (1 2 3 4)(5 6) = (1 2)(1 3)(1 4)(5 6), (1 2 3 4)(5 6) = (2 3)(2 4)(2 1)(5 6),
vagy
de mivel (1 2 3 4) = (2 3 4 1), ezért (1 2 3 4)(5 6) = (2 3)(5 6)(2 4)(2 1), mert idegen
transzpozíciók felcserélhet®k.
30. Tétel. Minden permutáció vagy csak páros vagy csak páratlan sok transzpozíció szorzataként írható fel. 31. De níció.
A
π ∈ Sn
permutációt párosnak nevezzük, ha felbontható páros sok transz-
pozíció szorzatára. A nempáros permutációkat páratlannak nevezzük. Továbbá de niáljuk:
( +1, sgn π = −1,
32. Kérdések. (1) (2) (3) (4) (5) (6) (7) (8)
ha ha
π π
páros, páratlan.
Az alábbi állítások közül melyek igazak és melyek hamisak?
Az identitás páros. Minden transzpozíció páratlan. Minden páros hosszú ciklus páros. Minden páratlan hosszú ciklus páros. Páros permutációk szorzata páros. Páratlan permutációk szorzata páros. Páros és páratlan permutáció szorzata páratlan. Páratlan permutációk inverze páratlan.
5
33. Példa.
4 × 4-gyes
Megmutatjuk, hogy a
tologatós játékban a baloldali kezd®állásból
nem lehet el®állítani a jobboldalit:
A=
1
2
3
4
2
1
3
4
5
6
7
8
5
6
7
8
9
10
11
12
9
10
11
12
13
14
15
13
14
15
B=
A játék minden állásához hozzárendeljük az az üres mez® helyébe a
16-os
S16
csoport egyik elemét, mégpedig úgy, hogy
számot képzeljük, és a kapott
a1 a2 a3 a4 a5 a6 a7 a8 T = a9 a10 a11 a12 a13 a14 a15 a16 táblázatot felhasználva képezzük a
πT =
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16
permutációt. Vegyük észre, hogy ha egy állapotban eltolunk egy négyzetet, akkor lényegében felcseréltük a
16-os
számot valamely másik számmal. Tehát egy transzpozíciót hajtottunk
végre, azaz az állapothoz rendelt permutáció paritása megváltozik. Mivel mind az a
B
A
mind
állapotban az üres mez® a jobb alsó sarokban van, ezért biztos hogy páros sok lépest
kell megtennünk
A-ból B -be
(ugyanannyiszor kell a 16-os számnak felfelé és lefelé, illetve
balra és jobbra mozognia). Páros sok lépes során a hozzárendelt permutáció paritása nem változik. De az
A
kezd®állapotra
πA = id ami páros, míg a jobboldali A állapotból a B állapotba jutni.
állapotra
πB = (1 2)
ami páratlan. Tehát nem lehet az
34. De níció. permutációk
n-edrend¶
Az Sn csoportot az n-edrend¶ szimmetrikus csoportnak nevezzük. A páros An = { π ∈ Sn : π páros } halmaza szintén csoportot alkot, amelynek neve az
alternáló csoport.
35. Kérdések. (1) (2) (3) (4)
Hány páratlan permutáció van Hány páros permutáció van
S3 -ban?
S3 -ban? S1 -ben? S1 -ben?
Hány páratlan permutáció van Hány páros permutáció van
36. Tétel.
Tetsz®leges
n ≥ 2 egészre |An | =
n! 2.
6
