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

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

${\displaystyle \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):

${\displaystyle \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:

${\displaystyle {\begin{pmatrix}3&4\end{pmatrix}}{\begin{pmatrix}1&2&5\end{pmatrix}}}$   eller   ${\displaystyle {\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

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

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

vara distinkta element i ${\displaystyle S}$. Uttrycket

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

betecknar cykeln σ vars verkan är

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

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

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

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

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

${\displaystyle (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

• Cykelindex

Referenser

• 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

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.