Zykeltyp

Graph einer Permutation vom Typ ${\displaystyle 1^{1}2^{1}4^{1}}$ oder ${\displaystyle (4,2,1)}$.

Die Permutation

${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5&6&7\\2&4&1&3&5&7&6\end{pmatrix}}=(1243)(5)(67)\in S_{7}}$

weist den Zykeltyp

${\displaystyle \operatorname {typ} (\pi )=1^{1}2^{1}3^{0}4^{1}5^{0}6^{0}7^{0}=1^{1}2^{1}4^{1}}$   oder   ${\displaystyle \operatorname {typ} (\pi )=\left(4,2,1\right)}$

auf, denn ihre Zykeldarstellung besteht aus je einem Zyklus der Länge eins, zwei und vier. Den gleichen Zykeltyp besitzt etwa auch die Permutation ${\displaystyle \pi =(1457)(36)(2)\in S_{7}}$.

Die folgenden Arten ${\displaystyle n}$-stelliger Permutationen ${\displaystyle \pi \in S_{n}}$ mit ${\displaystyle n\geq 2}$ besitzen jeweils den zugehörigen Zykeltyp:

• identische Permutation:

${\displaystyle \operatorname {typ} (\pi )=1^{n}}$   oder   ${\displaystyle \operatorname {typ} (\pi )=(1,\ldots ,1)}$

• Transpositionen (Vertauschungen):

${\displaystyle \operatorname {typ} (\pi )=1^{n-2}2^{1}}$   oder   ${\displaystyle \operatorname {typ} (\pi )=(2,1,\ldots ,1)}$

• zyklische Permutationen der Länge ${\displaystyle r\geq 2}$:

${\displaystyle \operatorname {typ} (\pi )=1^{n-r}r^{1}}$   oder   ${\displaystyle \operatorname {typ} (\pi )=(r,1,\ldots ,1)}$

• fixpunktfreie Permutationen:

${\displaystyle \operatorname {typ} (\pi )=2^{b_{2}}\ldots n^{b_{n}}}$   oder   ${\displaystyle \operatorname {typ} (\pi )=\left(k_{1},\ldots ,k_{s}\right)}$ mit ${\displaystyle k_{j}\geq 2}$ für alle ${\displaystyle j}$

• selbstinverse Permutationen:

${\displaystyle \operatorname {typ} (\pi )=1^{b_{1}}2^{b_{2}}}$   oder   ${\displaystyle \operatorname {typ} (\pi )=\left(k_{1},\ldots ,k_{s}\right)}$ mit ${\displaystyle k_{j}\leq 2}$ für alle ${\displaystyle j}$

Für die Anzahl und Längen der Zyklen einer ${\displaystyle n}$-stelligen Permutation gilt stets[1]

${\displaystyle 1\cdot b_{1}+2\cdot b_{2}+\ldots +n\cdot b_{n}=n}$,

demnach müssen für ${\displaystyle n\geq 2}$ manche der Zahlen ${\displaystyle b_{j}}$ gleich null sein. Für die Summe aller Zykellängen gilt entsprechend

${\displaystyle k_{1}+k_{2}+\ldots +k_{s}=n}$.

Daher entspricht die Anzahl der Zykeltypen in ${\displaystyle S_{n}}$ gerade der Anzahl der Partitionen der Zahl ${\displaystyle n}$,[4] die durch die Folge

${\displaystyle 1,2,3,5,7,11,\ldots }$   (Folge A000041 in OEIS)

gegeben ist. In der nebenstehenden Tabelle ist die Anzahl der Zykeltypen in ${\displaystyle S_{n}}$ die Zahl der Zeilen zu dem gegebenen ${\displaystyle n}$.

Die Anzahl der Permutationen ${\displaystyle \pi \in S_{n}}$ mit ${\displaystyle \operatorname {typ} (\pi )=1^{b_{1}}2^{b_{2}}\ldots n^{b_{n}}}$ beträgt[6]

${\displaystyle {\frac {n!}{b_{1}!\cdot b_{2}!\cdot \ldots \cdot b_{n}!\cdot 1^{b_{1}}\cdot 2^{b_{2}}\cdot \ldots \cdot n^{b_{n}}}}}$   (Folge A036039 in OEIS),

denn die Zyklen der Länge ${\displaystyle j}$ können auf ${\displaystyle b_{j}!}$ verschiedene Weisen angeordnet werden, wobei jeder dieser Zyklen auf ${\displaystyle j}$ verschiedene Weisen geschrieben werden kann. In der nebenstehenden Tabelle finden sich diese Anzahlen in der letzten Spalte. Unter Zuhilfenahme der Tupeldarstellung lässt sich die Anzahl der möglichen Permutationen eines gegebenen Zykeltyps auch durch

${\displaystyle {\frac {n!}{b_{1}!\cdot \ldots \cdot b_{n}!\cdot k_{1}\cdot \ldots \cdot k_{s}}}}$,

angeben. Verwandt dazu sind die Stirling-Zahlen erster Art ${\displaystyle s_{n,k}}$, die die Anzahl der ${\displaystyle n}$-stelligen Permutationen angeben, die genau ${\displaystyle k}$ Zyklen aufweisen. Die Stirling-Zahlen entstehen aus der Summe der Anzahlen der Permutationen mit gleicher Zyklenzahl.[6] Beispielsweise ist die Stirling-Zahl ${\displaystyle s_{5,2}=30+20=50}$, siehe die zweit- und drittletzte Zeile in der Tabelle.