Cyklisk notation

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, s på t och t på r. Hela permutationen kan sedan skrivas som en produkt av sådana cykliska partitioner.

Exempel redigera

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").

\sigma ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}

Skrivsättet innebär alltså att σ(1)=2, σ(2)=5 etc. Om man 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):

\sigma ={\begin{pmatrix}1&2&5\end{pmatrix}}{\begin{pmatrix}3&4\end{pmatrix}}

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:

{\begin{pmatrix}3&4\end{pmatrix}}{\begin{pmatrix}1&2&5\end{pmatrix}}

eller

{\begin{pmatrix}4&3\end{pmatrix}}{\begin{pmatrix}5&1&2\end{pmatrix}}.

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

Låt $S$ vara mängden $\{1,\dots ,n\},n\in \mathbb {N}$ , och

a_{1},\ldots ,a_{k},\quad 1\leq k\leq n

vara distinkta element i $S$ . Uttrycket

(a_{1}\ \ldots \ a_{k})

betecknar cykeln σ vars verkan är

a_{1}\mapsto a_{2}\mapsto a_{3}\mapsto \ldots \mapsto a_{k}\mapsto a_{1}.

För varje index $i:1\leq i\leq k$ gäller

\sigma (a_{i})=a_{i+1},

där med $a_{k+1}$ avses $a_{1}$ .

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

(a_{1}\ a_{2}\ a_{3}\ \ldots \ a_{k})=(a_{2}\ a_{3}\ \ldots \ a_{k}\ a_{1})=\cdots =(a_{k}\ a_{1}\ a_{2}\ \ldots \ a_{k-1}).\,

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

Cykelindex

Referenser redigera

I.N. Herstein, Topics in Algebra, Blaisdell Publishing Company, Waltham, Massachusetts, 1964.
Brualdi, Richard A. (2010), Introductory Combinatorics (5th), Prentice-Hall, ISBN 978-0-13-602040-0
Burnside, William (1897) Theory of Groups of Finite Order på Project Gutenberg
Dehn, Edgar (1960) [1930], Algebraic Equations, Dover
Fraleigh, John (2003), A first course in abstract algebra (7th), Addison Wesley, s. 88–90, ISBN 978-0-201-76390-4
Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures, W.H. Freeman & Co., ISBN 0-7167-1804-9
Hungerford, Thomas W. (1997), Abstract Algebra: An Introduction, Brooks/Cole, ISBN 978-0-03-010559-3
Johnson, James L. (2003), Probability and Statistics for Computer Science, Wiley Interscience, ISBN 978-0-471-32672-4

Noter redigera

^ 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.
^ på varandra följande
^ Hungerford 1997, p. 231.
^ Johnson 2003, p. 691.

[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] å varandra följande

[3] Hungerford 1997, p. 231.

[4] Johnson 2003, p. 691.

[1]

[2]

[3]

[4]