Cyklisk notation

Från Wikipedia
(Omdirigerad från Cykelnotation)
Hoppa till navigering Hoppa till sök

Inom kombinatorik är cyklisk notation eller cykelnotation ett sätt att beskriva en permutation genom att skriva om den med dess cykliska partitioner och ange strukturen av dessa. Resultatet av permutationen framgår därmed tydligare. Varje cyklisk partition skrivs inom parentes. Exempelvis betyder (r s t), att r avbildas på s, st och tr. Hela permutationen kan sedan skrivas som en produkt av sådana cykliska partitioner.

Exempel[redigera | redigera wikitext]

Tag en mängd bestående av fem element och betrakta nedanstående permutation σ skriven med Cauchys tvåradsnotation[1]. Den övre raden betecknar de ingående elementen 1, 2... 5 ("före permutationen") och den undre deras bild σ(1), σ(2)... σ(5) ("efter permutationen").

Skrivsättet innebär alltså att σ(1)=2, σ(2)=5 etc. Om närmare betraktar permutationen, så ser man att element nummer 4 och element nummer 3 "byter plats" (transposition) och att elementen 1, 2 och 5 kommer att "ersätta varandra i cirkel" (cyklisk permutation), det vill säga 3 och 4 respektive 1, 2 och 5 tillhör två disjunkta partitioner. Detta kan skrivas som en multiplikation av de två cykliska partitionerna (125) och (34):

Med detta skrivsätt framgår det att permutationen består av två partitioner, vilka element som ingår i respektive partition och hur de avbildas inom partitionen, det vill säga hur de "byter plats". Ordningen i vilken partitionerna anges i "multiplikationen" har ingen betydelse eftersom de är disjunkta, de saknar gemensamma element, och ej heller vilket av elementen inom partitionen som inleder uppräkningen, så länge ordningen i vilken de följer på varandra är densamma. Permutationen ovan kan således även skrivas som:

  eller  

Som ett ytterligare exempel kan vi ta speglingen av den regelbundna sexhörningen ABCDEF (med hörnen - eller om man så önskar sidorna - A, B, C, D, E och F) och speglingen av denna genom linjen som går genom A och D. Denna permutation kan skrivas (A)(BF)(CE)(D); A och D avbildas på sig själv (fixpunkter) och de övriga hörnen byter plats parvis. Om det framgår av sammanhanget, anger man ofta inte fixpunkterna: (BF)(CE). Identitetsavbildningen, t.ex. för fyra element (1)(2)(3)(4), skrivs i sådana fall ofta som () eller (1).

Skrivsättet kan även användas för att beteckna konsekutiva[2] permutationer. Om de ingående cyklerna inte är disjunkta leder dock den ordning de utförs i ofta till olika resultat. Man utläser då skrivsättet så att de utförs i den ordning de står från vänster till höger. Så ger t.ex. (ab)(ac) "resultatet" "bca" på strängen "abc" (först byter a och b plats, sedan a och c), medan (ac)(ab) i stället ger "cab". Detta kan såklart också uttryckas som (ab)(ac)=(abc)=(bca)=(cab) respektive (ac)(ab)=(acb)=(cba)=(bac). Av detta senare torde också framgå att alla cykliska permutationer kan skrivas som en produkt av transpositioner - t.ex. (abcdefg)=(ab)(ac)(ad)(ae)(af)(ag).

Definition[redigera | redigera wikitext]

Låt vara mängden , och

vara distinkta element i . Uttrycket

betecknar cykeln σ vars verkan är

För varje index gäller

där med avses .

Det finns olika uttryck för samma cykel; Nedanstående uttryck avser alla samma cykel:

En cykel som bara består av ett element, såsom exempelvis (3), är en identitetsavbildning.[3] Identitetsavbildningen kan också anges med den tomma cykeln, "()".[4]

Se även[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]

Noter[redigera | redigera wikitext]

  1. ^ Wussing, Hans (2007), The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory, Courier Dover Publications, s. 94, ISBN 9780486458687, http://books.google.com/books?id=Xp3JymnfAq4C&pg=PA94  - Cauchy använde denna form av notation för permutationer första gången 1815.
  2. ^ på varandra följande
  3. ^ Hungerford 1997, p. 231
  4. ^ Johnson 2003, p. 691