Anzahl

Anzahl der k-Zyklen in S_n

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	1	2	3	4	5	6	Summe
1	1						1
2	1	1					2
3	1	3	2				6
4	1	6	8	6			21
5	1	10	20	30	24		85
6	1	15	40	90	144	120	410

In der Menge der ${\displaystyle n!}$ verschiedenen Permutationen der Zahlen ${\displaystyle \{1,\dotsc ,n\}}$ gibt es genau ${\displaystyle (n-1)!}$ viele ${\displaystyle n}$-Zyklen. Jeder Permutation in Tupelschreibweise ${\displaystyle (i_{1},i_{2},\dotsc ,i_{n})}$ entspricht nämlich ein ${\displaystyle n}$-Zyklus ${\displaystyle (i_{1}~i_{2}~\dotso ~i_{n})}$, der wiederum auf ${\displaystyle n}$ verschiedene Weisen geschrieben werden kann. Bezeichnet nun allgemein ${\displaystyle Z_{n,k}}$ die Menge der ${\displaystyle k}$-Zyklen in ${\displaystyle S_{n}}$, dann gilt für ${\displaystyle k=2,\dotsc ,n}$

${\displaystyle |Z_{n,k}|={\binom {n}{k}}(k-1)!}$    (Folge A111492 in OEIS),

denn es gibt ${\displaystyle {\tbinom {n}{k}}}$ Möglichkeiten, ${\displaystyle k}$ von ${\displaystyle n}$ Zahlen auszuwählen. Für die Gesamtmenge ${\displaystyle Z_{n}}$ aller zyklischen Permutationen in ${\displaystyle S_{n}}$ inklusive der identischen Permutation gilt damit:

${\displaystyle |Z_{n}|=1+\sum _{k=2}^{n}{\binom {n}{k}}(k-1)!}$    (Folge A121726 in OEIS)

Kommutativität

Im Allgemeinen ist die Hintereinanderausführung zweier zyklischer Permutationen nicht kommutativ. Besitzen allerdings zwei zyklische Permutationen ${\displaystyle \pi _{i_{1},\dotsc ,i_{k}}\in Z_{n,k}}$ und ${\displaystyle \pi _{j_{1},\dotsc ,j_{l}}\in Z_{n,l}}$ disjunkte Träger, gilt also

${\displaystyle \{i_{1},\dotsc ,i_{k}\}\cap \{j_{1},\dotsc ,j_{l}\}=\emptyset }$,

dann lässt sich ihre Reihenfolge bei der Hintereinanderausführung vertauschen, das heißt, es gilt

${\displaystyle \pi _{i_{1},\dotsc ,i_{k}}\circ \pi _{j_{1},\dotsc ,j_{l}}=\pi _{j_{1},\dotsc ,j_{l}}\circ \pi _{i_{1},\dotsc ,i_{k}}}$.

Zyklische Permutationen mit disjunkten Trägern werden auch disjunkte Zyklen genannt.

Abgeschlossenheit und Inverse

Die Hintereinanderausführung zweier zyklischer Permutationen ist nicht notwendigerweise wieder zyklisch, wie das Beispiel

${\displaystyle \pi _{1234}\circ \pi _{1234}={\begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}}=\pi _{13}\circ \pi _{24}}$

zeigt. Daher bildet die Menge der zyklischen Permutationen ${\displaystyle Z_{n}}$ für ${\displaystyle n\geq 4}$ keine Untergruppe der symmetrischen Gruppe ${\displaystyle S_{n}}$. Allerdings ist die inverse Permutation einer zyklischen Permutation ${\displaystyle \pi _{i_{1},\dotsc ,i_{k}}}$ stets ebenfalls eine zyklische Permutation, nämlich diejenige, die die Zahlen ${\displaystyle i_{1},\dotsc ,i_{k}}$ in umgekehrter Reihenfolge zyklisch vertauscht, also

${\displaystyle (\pi _{i_{1},\dotsc ,i_{k}})^{-1}=\pi _{i_{k},\dotsc ,i_{1}}}$.

Die inverse Permutation einer Transposition ist damit wieder die gleiche Transposition.

Potenzen

Wird eine zyklische Permutation zweimal hintereinander angewandt, so verschieben sich alle Indizes zyklisch um ${\displaystyle 2}$, das heißt ${\displaystyle i_{1}}$ wird auf ${\displaystyle i_{3}}$ abgebildet, ${\displaystyle i_{2}}$ auf ${\displaystyle i_{4}}$ und so weiter bis hin zu ${\displaystyle i_{k-1}}$ auf ${\displaystyle i_{1}}$ und ${\displaystyle i_{k}}$ auf ${\displaystyle i_{2}}$. Allgemein verschieben sich durch die ${\displaystyle m}$-malige Anwendung einer zyklischen Permutation alle Indizes zyklisch um ${\displaystyle m}$. Die ${\displaystyle m}$-te Potenz einer zyklischen Permutation der Länge ${\displaystyle k}$ ist genau dann selbst wieder zyklisch, wenn ${\displaystyle m}$ und ${\displaystyle k}$ teilerfremd sind. Speziell ergibt die ${\displaystyle k}$-malige Anwendung einer zyklischen Permutation ${\displaystyle \pi \in Z_{n,k}}$ die identische Permutation, also

${\displaystyle \pi ^{k}=\operatorname {id} }$,

und die ${\displaystyle (k+1)}$-malige Anwendung ergibt wieder die Ausgangspermutation, also

${\displaystyle \pi ^{k+1}=\pi }$.

Daher bildet die Menge

${\displaystyle \{\pi ,\pi ^{2},\dotsc ,\pi ^{k-1},\pi ^{k}\}}$

mit der Hintereinanderausführung eine Untergruppe der symmetrischen Gruppe ${\displaystyle S_{n}}$, wobei ${\displaystyle \pi ^{k-j}}$ das inverse Element zu ${\displaystyle \pi ^{j}}$ ist. Diese Untergruppe ist isomorph zur zyklischen Gruppe ${\displaystyle C_{k}}$ und besteht genau dann ausschließlich aus zyklischen Permutationen, wenn ${\displaystyle k}$ eine Primzahl ist.

Konjugation

Für eine zyklische Permutation

${\displaystyle \pi =(i_{1}~i_{2}~\dotso ~i_{k})\in Z_{n,k}}$

berechnet sich die Konjugation mit einer beliebigen Permutation ${\displaystyle \sigma \in S_{n}}$ zu

${\displaystyle \sigma \circ \pi \circ \sigma ^{-1}=\left(\sigma (i_{1})~\sigma (i_{2})~\dotso ~\sigma (i_{k})\right)}$,

sie ergibt also wiederum einen ${\displaystyle k}$-Zyklus. Die Menge ${\displaystyle Z_{n,k}}$ bildet dabei für jedes ${\displaystyle k\in \{1,\dotsc ,n\}}$ eine Konjugationsklasse der Gruppe ${\displaystyle S_{n}}$. Allgemein sind zwei Permutationen ${\displaystyle \pi ,\sigma \in S_{n}}$ genau dann zueinander konjugiert, wenn ihr Zyklentyp übereinstimmt.

Zerlegung von Zyklen in Teilzyklen

Jede zyklische Permutation der Länge ${\displaystyle k>2}$ lässt sich an einer beliebigen Stelle ${\displaystyle l\in \{2,\dotsc ,k-1\}}$ mittels

${\displaystyle \pi _{i_{1},\dotsc ,i_{k}}=\pi _{i_{1},\dotsc ,i_{l}}\circ \pi _{i_{l},\dotsc ,i_{k}}}$

in zwei Teilzyklen zerlegen. Wendet man diese Zerlegung wiederholt mit ${\displaystyle l=2,3,\dotsc ,k-1}$ an, ergibt sich, dass jede zyklische Permutation der Länge ${\displaystyle k}$ mittels

${\displaystyle \pi _{i_{1},\dotsc ,i_{k}}=\pi _{i_{1},i_{2}}\circ \dotsb \circ \pi _{i_{k-1},i_{k}}}$

als Verkettung von ${\displaystyle k-1}$ Transpositionen geschrieben werden kann. Für das Vorzeichen einer zyklischen Permutation der Länge ${\displaystyle k}$ gilt damit

${\displaystyle \operatorname {sgn} (\pi _{i_{1},\dotsc ,i_{k}})=\operatorname {sgn} (\pi _{i_{1},i_{2}})\dotsm \operatorname {sgn} (\pi _{i_{k-1},i_{k}})=(-1)^{k-1}}$,

da Transpositionen immer ein ungerades Vorzeichen haben. Eine zyklische Permutation ist also genau dann gerade, wenn ihre Länge ungerade ist.

Zerlegung von Permutationen in Zyklen

Jede Permutation ${\displaystyle \pi \in S_{n}}$ lässt sich eindeutig (bis auf Vertauschung der Faktoren) als Verkettung von ${\displaystyle m\leq n}$ paarweise disjunkten Zyklen darstellen. Das heißt, es gilt

${\displaystyle \pi =\pi _{I_{1}}\circ \dotsb \circ \pi _{I_{m}}}$

mit paarweise disjunkten Trägern ${\displaystyle I_{j}=\{i_{j,1},\dotsc ,i_{j,n_{j}}\}}$ für ${\displaystyle j=1,\dotsc ,m}$, wobei ${\displaystyle n_{1}+\dotsb +n_{m}=n}$ ist. Die Stirling-Zahlen erster Art ${\displaystyle s_{n,m}}$ geben dabei an, wie viele Permutationen in ${\displaystyle S_{n}}$ als Verkettung von genau ${\displaystyle m}$ zyklischen Permutationen geschrieben werden können. Die Ordnung einer Permutation entspricht der Ordnung der zugehörigen zyklischen Gruppe und ist damit das kleinste gemeinsame Vielfache der Längen ${\displaystyle n_{1},\dotsc ,n_{m}}$ dieser Zyklen. Weiter ergibt sich das Vorzeichen einer Permutation aus der Zahl der Zyklen gerader Länge.