Polyatheorie Erik Verraedt 2011 - 2012
Inhoudsopgave 1 Inleiding
4
2 Enkele telproblemen 2.1 Probleem 1 . . 2.2 Probleem 2 . . 2.3 Probleem 3 . . 2.4 Probleem 4 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
5 5 5 6 6
3 Verband met acties 3.1 Voorbeeld . . . . . . . . . . . . 3.2 Acties . . . . . . . . . . . . . . 3.3 Orbietstelling . . . . . . . . . . 3.3.1 Toepassing orbietstelling 3.4 Stelling van Burnside . . . . . . 3.4.1 Toepassing: probleem 3
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
7 7 9 11 11 11 12
4 Stelling van Polya 4.1 Toepassing: probleem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13 14
5 Besluit
15
6 Bronnen
15
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
Polyatheorie
Erik Verraedt
1 Inleiding Op hoeveel manieren kan je de zijvlakken van een kubus kleuren met 2 kleuren? Wat als we dezelfde vraag met 3 kleuren stellen, om nog maar te zwijgen over 4, 5, 10, 100 kleuren? Kortom, hoe zit de vork in de steel als het gaat om het tellen van kleuringen van figuren (met een eindig aantal te kleuren oppervlakten) met een eindig aantal kleuren? In dit werk zullen we proberen een tipje van de sluier op te lichten. Gelukkig staan we er niet alleen voor: enkele wiskundigen hebben het ons reeds gemakkelijk gemaakt en het zware wiskundige werk gedaan. We zullen ons in de wereld van de zogenaamde Polyatheorie wagen, met als belangrijkste wiskundige vertegenwoordigers William Burnside (1852 - 1927) en George P`olya (1888 - 1985). Met behulp van heel wat groepentheorie zullen we werken naar een formule om telproblemen met kleuringen eenvoudig op te lossen. We zullen echter niet alle aspecten van de Polyatheorie belichten: naast de stelling van P`olya, waar we naartoe werken, bestaat er ook nog dezelfde stelling met gewichten, die gebruikt kan worden om complexere problemen op te lossen. Een voorbeeld van zo’n probleem is: Op hoeveel manieren kan je een kubus kleuren zodat deze 3 rode vlakken en 1 geel, 1 groen en 1 blauw vlak heeft? Om zulke problemen op te lossen is nog meer wiskundig inzicht en doorzettingsvermogen nodig dan voor wat we in dit werk behandelen. Gelukkig verschafte niemand minder dan George P`olya ons met een geldig excuus om deze problemen niet aan te snijden: If you can’t solve a problem, then there is an easier problem you can solve: find it. George P` olya Maar genoeg onwiskundige bladvulling, over tot het echte werk. En vergeet niet: Wiskunde, dat is pure ontspanning. - Hector Mommaerts
4
Polyatheorie
Erik Verraedt
2 Enkele telproblemen 2.1 Probleem 1 Gegeven is een vierkant verdeeld in 4 kleine vierkanten. Op hoeveel manieren kan je de 4 gebieden kleuren met hoogstens 2 kleuren? Rotaties van een bepaalde kleuring tellen niet als een aparte kleuring. 1 4
2 3
Met wat logisch nadenken vinden we snel dat het antwoord 6 is. We onderscheiden namelijk de volgende gevallen: Aantal vakjes met kleur 1 0 1 2 3 4
aantal mogelijke kleuringen 1 1 2 1 1
Als we aan 2 vakjes kleur 1 toekennen, zijn er 2 verschillende kleuringen mogelijk. De vakjes kunnen naast elkaar of op een diagonaal liggen. De andere gevallen geven telkens slechts 1 mogelijke kleuring.
2.2 Probleem 2 Gegeven is een kubus. Op hoeveel manieren kan je de zijvlakken inkleuren met ten hoogste 2 kleuren?
Ook hier vinden we eenvoudig de oplossing door een gevalsonderscheid. We vinden dat er 10 mogelijke kleuringen zijn. Aantal vakjes met kleur 1 0 1 2 3 4 5 6
aantal mogelijke kleuringen 1 1 2 2 2 1 1
Bij een verdeling met 2 vakjes in een bepaalde kleur hebben we de keuze:we kunnen deze tegenover elkaar plaatsen, of laten aansluiten. Met 3 vakjes in een kleur kunnen we de 3 vakjes rond een hoekpunt nemen, of 3 aaneensluitende vakjes waarvan de 2 uiterste geen ribbe gemeen hebben..
5
Polyatheorie
Erik Verraedt
2.3 Probleem 3 Op hoeveel manieren kan je het vierkant van probleem 1 kleuren met ten hoogste m kleuren? 1 4
2 3
We lossen dit op met een gevalsonderscheid. Juist 1 kleur: 1 mogelijke kleuring Juist 2 kleuren: 4 mogelijke kleuringen Juist 3 kleuren: 9 mogelijke kleuringen Juist 4 kleuren: 6 mogelijke kleuringen Dus voor ten hoogste m kleuren vinden we voor het aantal mogelijkheden 1 2 2 4 Cm · 1 + Cm · 4 + Cm · 9 + Cm · 6. 1 = m mogelijkheiden om onze kubus in 1 kleur te kleuren. Voor 2 kleuren We hebben immers Cm 2 . Aangezien we met nemen we alle mogelijke paren van kleuren uit onze m kleuren, dus Cm 2 · 4 mogelijkheden. Op analoge 2 kleuren 4 mogelijke kleuringen kunnen maken, geeft dit Cm wijze vervolledigen we zo onze formule. We kunnen deze formule uitwerken en op volgende wijze schrijven:
m4 + m2 + 2m . 4
2.4 Probleem 4 Op hoeveel manieren kan je de kubus van probleem 2 kleuren met ten hoogste m kleuren?
Dit probleem kunnen we met dezelfde strategie oplossen. Dit is echter niet effici¨ent en tijdrovend. We kunnen de volgende formule vinden: m2 · (m4 + 3m2 + 12m + 8) 24 Later zullen we in staat zijn deze formule op eenvoudige wijze te vinden.
6
Polyatheorie
Erik Verraedt
3 Verband met acties Terminologie 1. Een kleuring van een verzameling X met een verzameling K is een afbeelding k : X → K. Notatie: k ∈ K x
3.1 Voorbeeld Om deze notatie toe te lichten, nemen we het vierkant van probleem 1 onder de loep.
1 4
2 3
X = {1, 2, 3, 4} K = {kleuren} We geven enkele voorbeelden van kleuringen met K = {R, G}
1 R G
R G
Deze kleuring wordt gegeven door de volgende afbeelding:
k1 :
1 2 3
4
7→ R 7→ R 7→ G 7→ G
2 G G
R R
Deze kleuring wordt gegeven door de volgende afbeelding:
k2 :
1 2 3
4
7
7→ G 7→ R 7→ R 7→ G
Polyatheorie
Erik Verraedt
3 R G
G R
Deze kleuring wordt gegeven door de volgende afbeelding:
k3 :
1 2 3
4
7→ R 7→ G 7→ R 7→ G
We merken op dat bepaalde kleuringen hetzelfde zijn, namelijk dat men door draaiing van een kleuring een andere bekomt. Zo merken we dat k1 ∼ k2 en dat k1 6∼ k3 . Defini¨eren we de draaiing over 90◦ = (1234)1 als a, dan geldt dat k1 = k2 ◦a. Het is triviaal dat @n ∈ {0, 1, 2, 3} : k1 = k3 ◦an . We defini¨eren ∼ als volgt:
¶
©
ki ∼ kj ⇔ ∃r ∈ G ≡ Id, a, a2 , a3 ⊂ S(X) : ki = kj ◦ r waarbij S(X) de permutatiegroep van de figuur is. Dit is een equivalentierelatie, dat wil zeggen dat aan de volgende eigenschappen voldaan is: Voor alle x ∈ X geldt dat x ∼ x Voor alle x, y ∈ X geldt: als x ∼ y, dan y ∼ x Voor alle x, y, z ∈ X geldt: als x ∼ y en y ∼ z, dan x ∼ z
1
Vierkant 1 komt op 2, 2 op 3, 3 op 4 en 4 op 1. Dit noemen we de cykelschrijfwijze.
8
Polyatheorie
Erik Verraedt
3.2 Acties Definitie 3.1. Zij G, ∗ een groep en V een verzameling. Een rechtse actie van G op V is een afbeelding V × G → V : (v, g) 7→ v · g zodat ∀v ∈ V : v · e = v ∀v ∈ V ; ∀g1 , g2 ∈ G : v · (g1 ∗ g2 ) = (v · g1 ) · g2 .
N
We illustreren dit met het voorbeeld van de kubus: Neem V = K x , de verzameling kleuringen van de kubus, en G ⊂ S(X), ◦ de verzameling rotaties die we kunnen toepassen. Beschouw de rechtse actie K x × G → K x : (k, s) 7→ k · s = k ◦ s. Hierbij is k een kleuring die wordt uitgevoerd na de rotatie s. Er geldt: k · Idx = k ◦ Idx = k k · (s ◦ r) = k ◦ (s ◦ r) = (k ◦ s) ◦ r = (k · s) ◦ r = (k · s) · r We toetsen dit aan het gezond verstand: het is triviaal dat een kleuring toekennen na de identieke rotatie hetzelfde is als de kleuring toekennen aan de kubus. Het tweede punt is minder voor de hand liggend. We werken daarom een voorbeeld uit.
Beschouw de volgende rotaties:
a
s beeld het bovenvlak op het rechtse vlak af, het rechtse op het onderste, het onderste op het linkse en het linkse op het bovenste. Het voorvlak en achtervlak blijven op hun oorspronkelijke plaats: s = (3146). r beeld het bovenvlak op het linkse vlak af, het linkse op het onderste, het onderste op het rechtse en het rechtse op het bovenste. Het voorvlak en achtervlak blijven op hun oorspronkelijke plaats: r = (1364). We beschouwen de kleuring k die het bovenvlak blauw kleurt en het rechtervlak rood. k · (s ◦ r) = k, want r en s leveren ons terug de beginsituatie op. (k·s)·r splitsen we op. We merken dat k·s de kleuring is waarbij het linkervak blauw wordt gekleurd en het bovenvlak rood. Voeren we dus eerst r uit, dan wordt het bovenvlak op het linkervlak afgebeeld en het rechtervak op het bovenvlak. Wanneer we dan de kleuring k · s toepassen, wordt het bovenvlak blauw en het rechtervak rood, hetgeen gelijk is aan de kleuring k.
9
Polyatheorie
Erik Verraedt
Eigenschap 1. Een rechtse actie implementeert een equivalentierelatie op V : v1 ∼ v2 ⇔ ∃g ∈ G : v1 · g = v2 We bewijzen dit door middel van de 3 criteria van een equivalentierelatie. Bewijs.
v1 ∼ v1
Ja, want v1 · e = v1 .
v1 ∼ v2 ⇒ v2 ∼ v1 Stel v1 ∼ v2 . ∃g zodat v1 · g = v2 . Dan geldt dat v2 · g −1 = (v1 · g) · g −1 = v1 · (g ∗ g −1 ) = v1 · e = v1 Dus v2 ∼ v1 . Als v1 ∼ v2 en v2 ∼ v3 , dan is v1 ∼ v3 . Stel v1 , v2 , v3 zodat v1 ∼ v2 en v2 ∼ v3 . v1 · g1 = v2 v2 · g2 = v3 v3 = v2 · g2 = (v1 · g1 ) · g2 = v1 · (g1 ∗ g2 ) g1 ∗ g2 ∈ G v1 ∼ v3
Definitie 3.2. Stel dat G een rechtse actie uitvoert op een verzameling V . Or(v) = v · G = {v · G | g ∈ G} ⊂ V is de orbiet van v ∈ V . St(v) = {g ∈ G | v · g = v} is de stabilisator van v ∈ V , dit is een deelgroep van g ∈ G.
N
Nemen we als voorbeeld een kubus met het voorvlak in een andere kleur, dan is de orbiet de verzameling van draaiingen waarbij men een ander zicht verkrijgt. Het aantal elementen van Or(v), genoteerd als |Or(v)|, is dan 6. We kunnen immers het gekleurde vak op elk van de 6 zijden afbeelden. De stabilisator is de verzameling van draaiingen waarbij het zicht niet verandert. In dit geval kunnen we de kubus kantelen, zolang het voorvlak op dezelfde plaats blijft. We vinden dat |St(v)| = 4.
10
Polyatheorie
Erik Verraedt
3.3 Orbietstelling Stelling 3.3. (Orbietstelling) Stel dat een eindige groep G een actie uitvoert op een verzameling V. ∀v ∈ V : |G| = |Or(v)| · |St(v)| Terminologie 2. Een kleurpatroon bij een kleuring van de elementen van X door K is een orbiet van de actie van G ⊂ S(X) op K x . 3.3.1 Toepassing orbietstelling Wat is het aantal elementen van G ⊂ S(X) bij de kubus? M.O. ¶ © G = rotaties van de kubus in R3 ⊂ S6 G voert dus een rechtse actie uit op {1, 2, 3, 4, 5, 6}, namelijk: G × {1, 2, 3, 4, 5, 6} → {1, 2, 3, 4, 5, 6} : (s, i) 7→ s(i) Dus: |G| = |Or(1)| · |St(1)| = 6 · 4 = 24.
3.4 Stelling van Burnside Stelling 3.4. (Stelling van Burnside) Stel dat een eindige groep G een rechtse actie uitvoert op een eindige verzameling V . Dan is 1 X |F ix(g)| |G| g∈G
#orbieten = waarbij F ix(g) = {v ∈ V |v · g = v} . Bewijs. Noteer O = {Or(v)|v ∈ V }. Dan geldt:
1 X 1 X |F ix(g)| = # {v ∈ V |v · g = v} |G| g∈G |G| g∈G 1 # {(v, g) ∈ V × G|v · g = v} |G| 1 X # {g ∈ G|v · g = v} = |G| v∈V =
=
1 X |St(v)| |G| v∈V
=
X v∈V
=
1 |Or(v)|
X X 1 o∈O v∈O
=
X
|O|
1
o∈O
= |O| = #orbieten
11
Polyatheorie
Erik Verraedt
3.4.1 Toepassing: probleem 3 Oplossing van probleem 3 via de stelling van Burnside: # kleurpatronen van X = {1, 2, 3,4} met K (|K| = m) = # orbieten van de actie van G = Id, a, a2 , a3 op K x = ä 1 X 1Ä |F ix(g)| = |F ix(Id)| + |F ix(a)| + |F ix(a2 )| + |F ix(a3 )| |G| g∈G 4 ä 1Ä 4 m + m + m2 + m 4 m = (m3 + m + 1) 4
=
12
Polyatheorie
Erik Verraedt
4 Stelling van Polya Afspraak In de disjuncte cykelschrijfwijze van een element σ ∈ Sn , schrijven we de cykels van lengte ´e´en wel. Normaal gezien is dit niet nodig, omdat de niet vermelde vlakken op hun plaats blijven. Bij de stelling van Polya moete we echter tellen hoeveel cykels er voorkomen en welke lengte ze hebben. Om verwarring te vermijden schrijven we dus ook de cykels van lengte ´e´en. Notatie Zij σ ∈ Sn . c(σ) = aantal cykels in de disjuncte schrijfwijze van σ. ci (σ) = aantal cykels van lengte i in de disjuncte schrijfwijze van σ. Nemen we bij voorbeeld de volgende draaiing bij de kubus: a = (1265)(3)(4), dan vinden we dat c(a) = 3, c1 = 2 en c4 = 1.
a
Merk op dat
c(σ) =
n X
ci (σ).
i=1
Het is triviaal dat het aantal cykels gelijk is aan de som van het aantal cykels van elke mogelijke lengte. We vinden ook dat n n=
X
i · c1 (σ).
i=1
Ook dit spreekt voor zich. Bij het voorbeeld van de kubus en draaiing a geeft dit bijvoorbeeld het volgende: 6=
6 X
i · c1 (a) = 2 · 1 + 1 · 4.
i=1
Eigenschap 2. Zij X een eindige verzameling en G een deelgroep van S(X) die een actie uitvoert op K x met |K| = m. Dan geldt ∀g ∈ G : |F ix(g)| = mc(g) . Bewijs. Een kleuring k is vast onder g als voor elke cykel (in de disjuncte cykelschrijfwijze) van g geldt dat elk element in die cykel dezelfde kleur krijgt.
Stelling 4.1. (Stelling van Polya) Zij X een eindige verzameling, K een verzameling kleuren met m elementen. Zij G een deelgroep van S(X) die een actie uitvoert op K x . Dan is #kleurpatronen =
13
1 X c(g) m . |G| g
Polyatheorie
Erik Verraedt
4.1 Toepassing: probleem 4 We lossen probleem 4 op. Op hoeveel manieren kan je de kubus kleuren met ten hoogste m kleuren? Als kubus nemen we de dobbelsteen.
i ii ik l j it ig x
We beschouwen de identieke afbeelding. 7→
Id = (1)(2)(3)(4)(5)(6)
Draaiing rond een as door het midden van 2 overstaande vlakken.
7→
a = (1562)(3)(4)
7→
b = (16)(25)(3)(4)
7→
c = (1265)(3)(4)
Er zijn 3 mogelijke assen waarrond we op deze wijze kunnen draaien. Draaiing rond een as door het midden van 2 overstaande ribben. 7→
d = (16)(24)(35)
Er zijn 6 mogelijk assen waarrond we op deze wijze kunnen draaien. Draaiing rond een as door 2 hoekpunten. 7→
e = (145)(263)
7→
f = (154)(236)
Er zijn 4 mogelijke assen waarrond we op deze wijze kunnen draaien. Voor het aantal kleurpatronen met m kleuren kunnen we de formule nu toepassen: 1 X c(g) 1 X c(g) m = m |G| g 24 g
ó 1î 6 m + 3(m3 + m4 + m3 ) + 6m3 + 4(m2 + m2 ) 24 ó m2 î 4 = m + 3m3 + 12m + 8 24
=
14
Polyatheorie
Erik Verraedt
5 Besluit We merken dat we met behulp van de stelling van P`olya in staat zijn telproblemen, die op het eerste zicht misschien gemakkelijk zijn, op te lossen zonder alle mogelijkheden af te gaan. Met de stelling van P` olya met gewichten, die we kunnen verkrijgen via de stelling van Burnside met gewichten, zal het mogelijk zijn nog andere telproblemen op te lossen, met name telproblemen waar het van belang is hoeveel vlakken een bepaalde kleur krijgen. We hebben dus nog maar een kleine stap gezet in het verhaal van de Polyatheorie, maar een goed begin is het halve werk. . .
6 Bronnen Dit eindwerk is gebaseerd op de cursus discrete wiskunde van Prof. Dr. W. Veys, docent aan de KU Leuven. Het onderdeel Polyatheorie is ´e´en van de wiskundige topics die hierin behandeld worden, naast o.a. het duivenhokprincipe en cryptografie. De cursus wordt gegeven in het laatste jaar van de bachelor wiskunde.
15
