] >
Zij een eindige verzameling en laten en elementen van zijn met . De verwisseling , zie Definitie 3.19, van en is de -cykel . Het is een permutatie van .
10.16 Definitie. Zij een permutatie van een eindige verzameling . Het teken van , , is gedefinieerd door
De permutatie heet even als , dus als even is. Is , dus is oneven, dan noemen we oneven. ( is de verzameling van banen van in .)
Bewijs. De banen van bestaan op één na alle uit slechts één element. De enige andere baan heeft twee elementen. Dus , zodat . □
10.18 Voorbeeld. De permutatie van is een permutatie van een verzameling met elementen en heeft banen, dus . Het is een oneven permutatie.
Bewijs.
Stel en zitten in dezelfde baan van , zeg deze baan bestaat uit de volgende elementen van :
(met ). De baan van onder is dan
en de baan van onder is
De andere banen van zijn tevens banen van .
Dus is het aantal banen van één groter dan van als . Zie Figuur 10.3.
Stel en zitten in verschillende banen van . Laat de baan van onder zijn
en de baan van
Dan is de baan van onder
De andere banen van zijn tevens banen van .
Dus is het aantal banen van één kleiner dan van als niet . Zie ook voor dit geval Figuur 10.3. (In deze figuur is niet aangegeven of en in dezelfde baan zitten.) □
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
10.21 Propositie. Zij een permutatie van een eindige verzameling , dan is een product van verwisselingen. (We beschouwen de identieke permutatie als een product van verwisselingen.)
Bewijs. Heeft een baan met meer dan één element, kies dan twee elementen en uit die baan. Het aantal banen van is dan groter dan het aantal banen van . Herhaal dit proces. Het stopt zodra alle banen uit element bestaan (en er dus banen zijn). Dan , waarbij . De permutatie is dan een product van verwisselingen:
Het is duidelijk dat het kleinste aantal verwisselingen is dat nodig is voor .
De code, die we toevoegen aan combinatorics.py, levert van een permutatie een lijst van een minimaal aantal verwisselingen waarvan het product de permutatie is.
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
M.a.w.: een even permutatie kan alleen als product van een even aantal verwisselingen geschreven worden, en een oneven permutatie alleen als product van een oneven aantal verwisselingen.
Even permutaties zijn dus producten van een even aantal verwisselingen. Een -cykel is even. Producten van -cykels zijn dat dan ook. In feite krijg je zo alle even permutaties:
10.25 Stelling. Zij een eindige verzameling met . Dan is iedere even permutatie een product van -cykels.
Bewijs. Laat een even permutatie zijn. Dan is een product van een even aantal verwisselingen. Voor een tweetal opeenvolgende factoren in zo’n product zijn er de volgende mogelijkheden
Nemen we de factoren twee aan twee bij elkaar, dan kunnen we een product van verwisselingen omschrijven naar een product van -cykels. □
Het teken van een permutatie is tot de macht het aantal elementen minus het aantal banen.
De schuifpuzzel van Voorbeeld 1.9 is in 1878 door Sam Loyd geïntroduceerd. Bij de puzzel waren de blokjes in de goede volgorde met uitzondering van de laatste twee. Daarom staat de puzzel bekend als de 14-15-puzzel. Loyd loofde $1000 uit voor de oplossing, wetend dat de puzzel onoplosbaar is. Het resultaat was een wereldwijde gekte. Bedrijven moesten het personeel verbieden er tijdens kantooruren mee bezig te zijn.
Samuel Loyd (Philadelphia 1841 – New York 1911)
We hebben een verzameling met blokjes, waaronder ‘virtueel’ blokje, en een verzameling met de mogelijke plaatsen voor de blokjes. Een stand van de puzzel is een bijectie . Om de stand te coderen nummeren we de blokjes en de plaatsen:
We nummeren de blokjes zo dat het virtuele blokje is. In de puzzel staan de nummers van de echte blokjes op het blokje. Die nummering ligt dus vast.
Een stand kunnen we nu koppelen aan een permutatie van :
Een stand correspondeert met een permutatie van :
Laten we met de stand aangeven waarbij voor iedere blokje op plaats staat.
Van de puzzel is een graaf te maken. De hoekpunten zijn de standen , het zijn er . We beschrijven nu de ribben. Is een permutatie van , dan staat in de stand blokje op plaats : was de plaats eerst , dan is hij nu . Als we [] door [] vervangen, dan veranderen we de plaatsen van de blokjes dus volgens . Zo kom je van een stand in een nieuwe stand. Het hangt van af welke zetten vanuit mogelijk zijn. Het zijn er twee, drie of vier, afhankelijk van de plaats van blokje . Elk van die zetten correspondeert met een verwisseling van met een ander getal.
Doen we een reeks van zetten uitgaande van een stand dan wordt bij iedere zet van links met een verwisseling vermenigvuldigd ( = samengesteld). Is de plaats van na die reeks van zetten weer , d.w.z. dezelfde als bij de oorspronkelijke stand, dan is blokje bij een even aantal zetten in verticale richting verplaatst en ook bij een even aantal zetten in horizontale richting. In totaal is dit een even aantal verwisselingen. Is het resultaat van de zettenreeks, dan hebben en dus hetzelfde teken. De 14-15-puzzel is dus niet oplosbaar: begin- en eindstand schelen verwisseling.
Om in te zien dat de 14-15-puzzel niet oplosbaar is, was het niet nodig een explicite nummering van de plaatsen te geven. Nu is het handig om dat wel te doen. De plaatsnummers staan aangegeven in Figuur 10.5. In die figuur is voor iedere geplaatst op plaats . Bij deze nummering van de plaatsen is in Figuur 10.5 dus de stand weergegeven. Door het doen van zetten krijgen we uit deze stand standen . We weten al dat voor standen met geldt dat de permutatie even is. We zullen aantonen dat alle standen met even en bereikt kunnen worden. Een zet doen betekent verwisselen met een aangrenzend blokje. Bij een reeks van zetten verplaatst zich over het -veld. We kijken naar reeksen zetten waarbij weer op terugkomt. Twee van zulke reeksen achter elkaar is ook zo’n reeks. Kunnen we standen en bereiken (dit zijn dus standen met ), dan kan ook stand bereikt worden. Legt de weg af langs achtereenvolgens de plaatsen , , , , , , , , , , , , , , en tenslotte in terugkomt, dan is de nieuwe stand , waarbij
Bij de weg , , , hoort de permutatie
Omdat voor geldt
volgt nu uit Lemma 10.26 hieronder dat iedere stand met even bereikt kan worden.
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □