Zykeltyp

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

Der Typ (auch Zykeltyp) einer Permutation ist in der Kombinatorik und der Gruppentheorie eine wichtige Eigenschaft von Permutationen. Er beschreibt die Längen der einzelnen Zyklen in der Zykeldarstellung einer Permutation. Die Anzahl der möglichen Typen $n$-stelliger Permutationen entspricht der Anzahl der Zahlpartitionen von $n$. Die Anzahl der Permutationen pro Typ kann direkt aus der Typbeschreibung errechnet werden. Die Permutationen gleichen Typs bilden die Konjugationsklassen der symmetrischen Gruppe $S_{n}$.

Definition

Ist $S_{n}$ die symmetrische Gruppe der Permutationen, dann lässt sich jede Permutation $\pi \in S_{n}$ eindeutig (bis auf Vertauschung der Faktoren) als Komposition von höchstens $n$ paarweise disjunkten Zyklen darstellen. Bezeichnet nun $b_{j}$ für $j=1,\ldots ,n$ die Anzahl der Zyklen der Länge $j$ in $\pi$, dann ist der Typ einer Permutation der formale Ausdruck

$1^{b_{1}}2^{b_{2}}\ldots n^{b_{n}}$,

wobei die Terme mit $b_{j}=0$ nicht aufgeführt werden müssen. Teilweise wird der Ausdruck auch mit eckigen Klammern versehen. Formal heißt hier, dass das Produkt und die Potenzen nicht tatsächlich ausgerechnet werden. Eine alternative Darstellung des Typs einer Permutation ist das $s$-Tupel

$\left(k_{1},k_{2},\ldots ,k_{s}\right)$,

wobei $s\leq n$ und $k_{1}\geq \ldots \geq k_{s}\in \mathbb {N}$ die Längen der Zyklen in der Zykeldarstellung von $\pi$ in absteigender Reihenfolge sind. Gelegentlich werden die Zyklenlängen auch in aufsteigender Reihenfolge notiert. Beide Darstellungen beinhalten die gleichen Informationen über eine Permutation und können einfach ineinander umgewandelt werden.

Beispiele

Konkrete Beispiele

Die Permutation

$\pi ={\begin{pmatrix}1&2&3&4&5\\3&4&5&2&1\end{pmatrix}}=(135)(24)\in S_{5}$

weist den Typ

$1^{0}2^{1}3^{1}4^{0}5^{0}=2^{1}3^{1}$   bzw.   $\left(3,2\right)$

auf, denn ihre Zykeldarstellung besteht aus einer Permutation der Länge zwei und einer Permutation der Länge drei. Den gleichen Typ besitzt etwa auch die Permutation $(345)(12)\in S_{5}$.

Allgemeinere Beispiele

Die folgenden Arten $n$-stelliger Permutationen mit $n\geq 2$ besitzen jeweils den Typ:

• Identische Permutation:

$1^{n}$   oder   $(1,\ldots ,1)$

• Transpositionen (Vertauschungen):

$1^{n-2}2^{1}$   oder   $(2,1,\ldots ,1)$

• Zyklische Permutationen der Länge $r\geq 2$

$1^{n-r}r^{1}$   oder   $(r,1,\ldots ,1)$

• Fixpunktfreie Permutationen:

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

• Selbstinverse Permutationen:

$1^{b_{1}}2^{b_{2}}3^{0}\ldots n^{0}$   oder   $\left(k_{1},\ldots ,k_{s}\right)$ mit $k_{j}\leq 2$ für alle $j$

Anzahlen

$n$	Typ		Zykelstruktur	Anzahl
$1$	$1^{1}$	$\left(1\right)$	$(\cdot )$	$1$
$2$	$1^{2}$	$\left(1,1\right)$	$(\cdot )(\cdot )$	$1$
	$2^{1}$	$\left(2\right)$	$(\cdot \;\,\cdot )$	$1$
$3$	$1^{3}$	$\left(1,1,1\right)$	$(\cdot )(\cdot )(\cdot )$	$1$
	$1^{1}2^{1}$	$\left(2,1\right)$	$(\cdot \;\,\cdot )(\cdot )$	$3$
	$3^{1}$	$\left(3\right)$	$(\cdot \,\cdot \,\cdot )$	$2$
$4$	$1^{4}$	$\left(1,1,1,1\right)$	$(\cdot )(\cdot )(\cdot )(\cdot )$	$1$
	$1^{2}2^{1}$	$\left(2,1,1\right)$	$(\cdot \;\,\cdot )(\cdot )(\cdot )$	$6$
	$2^{2}$	$\left(2,2\right)$	$(\cdot \;\,\cdot )(\cdot \;\,\cdot )$	$3$
	$1^{1}3^{1}$	$\left(3,1\right)$	$(\cdot \;\cdot \;\cdot )(\cdot )$	$8$
	$4^{1}$	$\left(4\right)$	$(\cdot \;\cdot \;\cdot \;\,\cdot )$	$6$
$5$	$1^{5}$	$\left(1,1,1,1,1\right)$	$(\cdot )(\cdot )(\cdot )(\cdot )(\cdot )$	$1$
	$1^{3}2^{1}$	$\left(2,1,1,1\right)$	$(\cdot \;\,\cdot )(\cdot )(\cdot )(\cdot )$	$10$
	$1^{1}2^{2}$	$\left(2,2,1\right)$	$(\cdot \;\,\cdot )(\cdot \;\,\cdot )(\cdot )$	$15$
	$1^{2}3^{1}$	$\left(3,1,1\right)$	$(\cdot \;\cdot \;\cdot )(\cdot )(\cdot )$	$20$
	$2^{1}3^{1}$	$\left(3,2\right)$	$(\cdot \;\cdot \;\cdot )(\cdot \;\,\cdot )$	$20$
	$1^{1}4^{1}$	$\left(4,1\right)$	$(\cdot \;\cdot \;\cdot \;\,\cdot )(\cdot )$	$30$
	$5^{1}$	$\left(5\right)$	$(\cdot \;\cdot \;\cdot \;\cdot \;\cdot )$	$24$

Anzahl der Typen

Für die Anzahl der Zyklen einer $n$-stelligen Permutation gilt stets

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

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

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

Daher entspricht die Anzahl der Typen $n$-stelliger Permutationen gerade der Anzahl der Zahlpartitionen von $n$, die durch die Folge

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

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

Anzahl der Permutationen pro Typ

Die Anzahl der Permutationen vom Typ $1^{b_{1}}2^{b_{2}}\ldots n^{b_{n}}$ beträgt

${\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 $j$ können auf $b_{j}!$ verschiedene Weisen angeordnet werden, wobei jeder dieser Zyklen auf $j$ verschiedene Weisen geschrieben werden kann. In der nebenstehenden Tabelle finden sich diese Anzahlen in der letzten Spalte. Unter Zuhilfenahme der zweiten Darstellung $\left(k_{1},\ldots ,k_{s}\right)$ lässt sich die Anzahl der möglichen Permutationen eines gegebenen Typs auch durch

${\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 $s_{n,k}$, die die Anzahl der $n$-stelligen Permutationen angeben, die genau $k$ Zyklen aufweisen. Die Stirling-Zahlen entstehen aus der Summe der Anzahlen der Permutationen, deren Typ die gleiche Zyklenzahl aufweist. Beispielsweise ist die Stirling-Zahl $s_{5,2}=30+20=50$, siehe die zweit- und drittletzte Zeile in der Tabelle.

Zykelklassen

Die Permutationen gleichen Typs bilden Äquivalenzklassen und man schreibt $\pi \sim \sigma$, wenn $\pi ,\sigma \in S_{n}$ den gleichen Typ besitzen. Für die inverse Permutation $\pi ^{-1}$ einer Permutation $\pi$ gilt immer

$\pi ^{-1}\sim \pi$,

denn durch die Invertierung drehen sich nur die Reihenfolgen der Zahlen innerhalb der einzelnen Zyklen um. Zwar ist die Hintereinanderausführung zweier Permutationen $\pi ,\sigma$ im Allgemeinen nicht kommutativ, aber es gilt stets

$\pi \circ \sigma \sim \sigma \circ \pi$,

das Resultat weist also unabhängig von der Reihenfolge den gleichen Typ auf. Auch durch Konjugation mit einer beliebigen Permutation $\sigma$ ändert sich der Typ einer Permutation nicht, das heißt

$\sigma \circ \pi \circ \sigma ^{-1}\sim \pi$.

Allgemein sind zwei Permutationen sogar genau dann konjugiert, wenn sie vom gleichen Typ sind. Die $n$-stelligen Permutationen gleichen Typs bilden daher die Konjugationsklassen der symmetrischen Gruppe $S_{n}$.

Siehe auch

• Young-Tableau
• Zyklenzeiger

Literatur

• Martin Aigner: Diskrete Mathematik. Vieweg, 2006, ISBN 3-8348-9039-1. 
• Michael Artin: Algebra. Springer, 1998, ISBN 3-7643-5938-2. 
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. de Gruyter, 2003, ISBN 3-11-016727-1. 
• Hans Kurzweil, Bernd Stellmacher: Theorie der endlichen Gruppen: eine Einführung. Springer, 1998, ISBN 3-540-60331-X. 
• Kristina Reiss, Gernot Stroth: Endliche Strukturen. Springer, 2011, ISBN 3-642-17181-8.