] > Het teken van een permutatie [volgende][vorige][inhoud]                        (versie: 23 augustus 2011)

10.5  Het teken van een permutatie

Zij A een eindige verzameling en laten a en b elementen van A zijn met ab. De verwisseling τa,b, zie Definitie 3.19, van a en b is de 2-cykel (ab). Het is een permutatie van A.

10.16 Definitie. Zij σ een permutatie van een eindige verzameling A. Het teken van σ, sgn(σ), is gedefinieerd door

sgn(σ) = (1)#(A)#(Aσ).

De permutatie σ heet even als sgn(σ) = 1, dus als #(A) #(Aσ) even is. Is sgn(σ) = 1, dus is #(A) #(Aσ) oneven, dan noemen we σ oneven. (Aσ is de verzameling van banen van σ in A.)

10.17 Lemma. Zij σ een verwisseling in een eindige verzameling A. Dan sgn(σ) = 1.

Bewijs.   De banen van σ bestaan op één na alle uit slechts één element. De enige andere baan heeft twee elementen. Dus #(Aσ) = #(A) 1, zodat sgn(σ) = (1)1 = 1. □

10.18 Voorbeeld. De permutatie σ = 1 2 4 3 5 van 5¯ is een permutatie van een verzameling met 5 elementen en heeft 2 banen, dus sgn(σ) = (1)52 = 1. Het is een oneven permutatie.

10.19 Lemma. Zij σ een permutatie van een eindige verzameling A, en laten a en b elementen van A zijn. Dan

#(A(ab)σ) = #(Aσ) + 1 als a σb #(Aσ) 1  als niet a σb.

Bewijs.  

Stel a en b zitten in dezelfde baan van σ, zeg deze baan bestaat uit de volgende n elementen van A:

a,σ(a),σ2(a),,σk(a)(= b),,σn1(a)

(met 0 < k < n). De baan van a onder a b σ is dan

{a,σ(a),,σk1(a)},

en de baan van b onder a b σ is

{σk(a)(= b),σk+1(a),,σn1(a)}.

De andere banen van σ zijn tevens banen van a b σ.

Dus is het aantal banen van a b σ één groter dan van σ als a σb. Zie Figuur 10.3.

Stel a en b zitten in verschillende banen van σ. Laat de baan van a onder σ zijn

{a,σ(a),σ2(a),,σn1(a)},

en de baan van b

{b,σ(b),σ2(b),,σm1(b)}.

Dan is de baan van a onder a b σ

{a,σ(a),,σn1(a),b,σ(b),,σm1(b)}.

De andere banen van σ zijn tevens banen van a b σ.

Dus is het aantal banen van a b σ één kleiner dan van σ als niet a σb. Zie ook voor dit geval Figuur 10.3. (In deze figuur is niet aangegeven of a en b in dezelfde baan zitten.) □


SVG-Viewer needed.


Figuur 10.3: Samenstelling met verwisseling (ab)

10.20 Gevolg. Zij σ een permutatie van een eindige verzameling A, en zij τ een verwisseling van A. Dan

sgn(τσ) = sgn(σ).

Bewijs.  In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □

10.21 Propositie. Zij σ een permutatie van een eindige verzameling A, dan is σ een product van #(A) #(Aσ) verwisselingen. (We beschouwen de identieke permutatie als een product van 0 verwisselingen.)

Bewijs.   Heeft σ een baan met meer dan één element, kies dan twee elementen a1 en b1 uit die baan. Het aantal banen van a1 b1 σ is dan 1 groter dan het aantal banen van σ. Herhaal dit proces. Het stopt zodra alle banen uit 1 element bestaan (en er dus #(A) banen zijn). Dan ak bk ak1 bk1 a1 b1 σ = 1A, waarbij k = #(A) #(Aσ). De permutatie σ is dan een product van k verwisselingen:

σ = a1 b1 a2 b2 ak bk .

Het is duidelijk dat #(A) #(Aσ) het kleinste aantal verwisselingen is dat nodig is voor σ.

Python

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.

  def transpositions(perm):
      trans = []
      newperm = perm[:]
      identity = range(1, len(perm) + 1)
      while newperm!=identity:
          j = [i+1==newperm[i] for i in
          range(len(newperm))].index(0)
          trans.append((j + 1, newperm[j]))
          newperm[newperm.index(j+1)]=newperm[j]
          newperm[j] = j + 1
      return trans
  >>> transpositions([4,6,8,10,13,11,9,7,1,2,5,12,3])
  [(1, 4), (2, 6), (3, 8), (4, 10), (5, 13), (6, 11), (7, 9), (8, 9),
   (9, 10), (10, 11), (11, 13)]

10.22 Stelling. Laten σ en τ permutaties zijn van een eindige verzameling A. Dan:

sgn(στ) = sgn(σ)sgn(τ).

Bewijs.  In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □

10.23 Voorbeeld. We schrijven σ = 1 2 3 5 4 6 7 als product van verwisselingen.

1 2 σ = 2 3 5 4 6 7 2 3 1 2 σ = 3 5 4 6 7 3 5 2 3 1 2 σ = 4 6 7 4 6 3 5 2 3 1 2 σ = 6 7 6 7 4 6 3 5 2 3 1 2 σ = (1)

Dus σ = 1 2 2 3 3 5 4 6 6 7 .

10.24 Stelling. Zij σ = σ1σm met σ1,,σm verwisselingen. Dan

 m is even σ is een even permutatie.

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 3-cykel is even. Producten van 3-cykels zijn dat dan ook. In feite krijg je zo alle even permutaties:

10.25 Stelling. Zij A een eindige verzameling met #(A) 3. Dan is iedere even permutatie een product van 3-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 3-cykels. □

Python

Het teken van een permutatie is 1 tot de macht het aantal elementen minus het aantal banen.

  def sign(perm):
      return (-1)**(len(perm) - len(cycledecomposition(perm)))
  >>> sign([12,1,13,4,5,9,7,6,3,2,8,10,11])
  1

De 14-15-puzzel van Sam Loyd

SVG-Viewer needed.


Figuur 10.4: 14-15-puzzel

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)


Samuel Loyd was actief in de recreatieve wiskunde. Hij ontwierp vele puzzels, waarvan sommige wereldwijd bekend zijn geworden. Een andere bekende puzzel is de ‘Get of the World’-puzzel.

Zie The MacTutor History of Mathematics archive voor meer over Loyd.


Codering van standen en zetten

We hebben een verzameling  Blokjes met 16 blokjes, waaronder 1 ‘virtueel’ blokje, en een verzameling  Plaatsen met de 16 mogelijke plaatsen voor de blokjes. Een stand van de puzzel is een bijectie f :  Blokjes  Plaatsen. Om de stand te coderen nummeren we de blokjes en de plaatsen:

 blokje: 16¯  Blokjes en plaats: 16¯  Plaatsen.

We nummeren de blokjes zo dat  blokje(16) het virtuele blokje is. In de puzzel staan de nummers van de echte blokjes op het blokje. Die nummering ligt dus vast.

Een stand f kunnen we nu koppelen aan een permutatie van 16¯:

16¯ σ 16¯ blokje blokje  plaats plaats  Blokjes f  Plaatsen

Een stand f :  Blokjes  Plaatsen correspondeert met een permutatie σ van 16¯:

σ(i) = jf( blokje(i)) =  plaats(j).

Laten we met [σ] de stand aangeven waarbij voor iedere i blokje i op plaats σ(i) staat.

Van de puzzel is een graaf te maken. De hoekpunten zijn de standen [σ], het zijn er 16!. We beschrijven nu de ribben. Is τ een permutatie van 16¯, dan staat in de stand [τσ] blokje i op plaats τ(σ(i)): was de plaats eerst j, dan is hij nu τ(j). 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 σ(16) af welke zetten vanuit [σ] mogelijk zijn. Het zijn er twee, drie of vier, afhankelijk van de plaats van blokje 16. Elk van die zetten correspondeert met een verwisseling van 16 met een ander getal.

Waarom de 14-15-puzzel niet oplosbaar is

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 16 na die reeks van zetten weer σ(16), d.w.z. dezelfde als bij de oorspronkelijke stand, dan is blokje 16 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 1 verwisseling.

Welke standen wel bereikt worden

SVG-Viewer needed.


Figuur 10.5: nummering plaatsen

Om in te zien dat de 14-15-puzzel niet oplosbaar is, was het niet nodig een explicite nummering van de 16 plaatsen te geven. Nu is het handig om dat wel te doen. De plaatsnummers staan aangegeven in Figuur 10.5. In die figuur is  blokje(i) voor iedere i geplaatst op plaats i. Bij deze nummering van de plaatsen is in Figuur 10.5 dus de stand [(1)] weergegeven. Door het doen van zetten krijgen we uit deze stand standen [τ]. We weten al dat voor standen [τ] met τ(16) = 16 geldt dat de permutatie τ even is. We zullen aantonen dat alle standen [τ] met τ even en τ(16) = 16 bereikt kunnen worden. Een zet doen betekent  blokje(16) verwisselen met een aangrenzend blokje. Bij een reeks van zetten verplaatst  blokje(16) zich over het 4 × 4-veld. We kijken naar reeksen zetten waarbij  blokje(16) weer op  plaats(16) terugkomt. Twee van zulke reeksen achter elkaar is ook zo’n reeks. Kunnen we standen [τ1] en [τ2] bereiken (dit zijn dus standen met τ1(16) = τ2(16) = 16), dan kan ook stand [τ1τ2] bereikt worden. Legt  blokje(16) de weg af langs achtereenvolgens de plaatsen 2, 1, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3 en tenslotte in 16 terugkomt, dan is de nieuwe stand [σ], waarbij

σ = (123456789101112131415).

Bij de weg 2, 1, 3, 16 hoort de permutatie

ρ = 1 2 3 .

Omdat voor k 12 geldt

σkρσk = k + 1 k + 2 k + 3 ,

volgt nu uit Lemma 10.26 hieronder dat iedere stand [τ] met τ even bereikt kan worden.

10.26 Lemma. Zij met n 3. Dan is iedere even permutatie van n¯ een product van 3-cykels van de vorm k k + 1 k + 2 met k n2.

Bewijs.  In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □

[volgende][vorige][inhoud