Zykeltyp

Der Zykeltyp, kurz Typ, ist in der Kombinatorik und der Gruppentheorie eine wichtige Eigenschaft von Permutationen. Der Zykeltyp beschreibt die Anzahl und Längen der Zyklen in der Zykeldarstellung einer Permutation. Die Anzahl der möglichen Typen $n$-stelliger Permutationen entspricht gerade der Anzahl der Partitionen der Zahl $n$. Die Anzahl der Permutationen pro Zykeltyp kann aus der Typbeschreibung errechnet werden, wobei die Permutationen mit gleicher Zyklenzahl durch die Stirling-Zahlen erster Art gezählt werden.

Die inverse Permutation weist immer den Typ der Ausgangspermutation auf. Auch das Ergebnis der Komposition zweier Permutationen besitzt unabhängig von der Reihenfolge der Operanden immer den gleichen Zykeltyp. Weiter sind zwei Permutationen genau dann zueinander konjugiert, wenn sie vom gleichen Typ sind. Die Permutationen gleichen Zykeltyps bilden demnach die Konjugationsklassen der symmetrischen Gruppe vom Grad $n$.

Definition

Jede Permutation der symmetrischen Gruppe $S_n$ lässt sich eindeutig (bis auf Vertauschung der Faktoren) als Komposition von höchstens $n$ paarweise disjunkten Zyklen darstellen. Bezeichnet nun $b_j$ für $j=1,\dots ,n$ die Anzahl der Zyklen der Länge $j$ einer Permutation $\pi \in S_n$, dann ist der Zykeltyp dieser Permutation der formale Ausdruck

$\mathrm{typ}(\pi )=1^{b_1}{2}^{b_2}\dots n^{b_n}$,

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

$\mathrm{typ}(\pi )=(k_1,k_2,\dots ,k_s)$,

wobei $s\le n$ und $k_1\ge \dots \ge k_s\in \mathbb{N}$ die Längen der Zyklen in der Zykeldarstellung der Permutation 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

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

Die Permutation

$\pi =\left(\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ 2& 4& 1& 3& 5& 7& 6\end{array}\right)=(1243)(5)(67)\in S_7$

weist den Zykeltyp

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

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

Allgemeinere Beispiele

Die folgenden Arten $n$-stelliger Permutationen $\pi \in S_n$ mit $n\ge 2$ besitzen jeweils den zugehörigen Zykeltyp:

• identische Permutation:

$\mathrm{typ}(\pi )=1^n$   oder   $\mathrm{typ}(\pi )=(1,\dots ,1)$

• Transpositionen (Vertauschungen):

$\mathrm{typ}(\pi )=1^{n-2}{2}^1$   oder   $\mathrm{typ}(\pi )=(2,1,\dots ,1)$

• zyklische Permutationen der Länge $r\ge 2$:

$\mathrm{typ}(\pi )=1^{n-r}{r}^1$   oder   $\mathrm{typ}(\pi )=(r,1,\dots ,1)$

• fixpunktfreie Permutationen:

$\mathrm{typ}(\pi )=2^{b_2}\dots n^{b_n}$   oder   $\mathrm{typ}(\pi )=(k_1,\dots ,k_s)$ mit $k_j\ge 2$ für alle $j$

• selbstinverse Permutationen:

$\mathrm{typ}(\pi )=1^{b_1}{2}^{b_2}$   oder   $\mathrm{typ}(\pi )=(k_1,\dots ,k_s)$ mit $k_j\le 2$ für alle $j$

Anzahlen

$n$	Zykeltyp		Zykelstruktur	Anzahl
1	11	(1)	( • )	1
2	12	(1,1)	( • ) ( • )	1
	21	(2)	( • • )	1
3	13	(1,1,1)	( • ) ( • ) ( • )	1
	11 21	(2,1)	( • • ) ( • )	3
	31	(3)	( • • • )	2
4	14	(1,1,1,1)	( • ) ( • ) ( • ) ( • )	1
	12 21	(2,1,1)	( • • ) ( • ) ( • )	6
	22	(2,2)	( • • ) ( • • )	3
	11 31	(3,1)	( • • • ) ( • )	8
	41	(4)	( • • • • )	6
5	15	(1,1,1,1,1)	( • ) ( • ) ( • ) ( • ) ( • )	1
	13 21	(2,1,1,1)	( • • ) ( • ) ( • ) ( • )	10
	11 22	(2,2,1)	( • • ) ( • • ) ( • )	15
	12 31	(3,1,1)	( • • • ) ( • ) ( • )	20
	21 31	(3,2)	( • • • ) ( • • )	20
	11 41	(4,1)	( • • • • ) ( • )	30
	51	(5)	( • • • • • )	24

Zahl der Typen

Für die Anzahl und Längen der Zyklen einer $n$-stelligen Permutation gilt stets

$1\cdot b_1+2\cdot b_2+\dots +n\cdot b_n=n$,

demnach müssen für $n\ge 2$ manche der Zahlen $b_j$ gleich null sein. Für die Summe aller Zykellängen gilt entsprechend

$k_1+k_2+\dots +k_s=n$.

Daher entspricht die Anzahl der Zykeltypen in $S_n$ gerade der Anzahl der Partitionen der Zahl $n$, die durch die Folge

$1,2,3,5,7,11,\dots$   (Vorlage:OEIS)

gegeben ist. In der nebenstehenden Tabelle ist die Anzahl der Zykeltypen in $S_n$ die Zahl der Zeilen zu dem gegebenen $n$.

Zahl der Permutationen pro Typ

Die Anzahl der Permutationen $\pi \in S_n$ mit $\mathrm{typ}(\pi )=1^{b_1}{2}^{b_2}\dots n^{b_n}$ beträgt

$\frac{n!}{b_1!\cdot b_2!\cdot \dots \cdot b_n!\cdot 1^{b_1}\cdot 2^{b_2}\cdot \dots \cdot n^{b_n}}$   (Vorlage: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 Tupeldarstellung lässt sich die Anzahl der möglichen Permutationen eines gegebenen Zykeltyps auch durch

$\frac{n!}{b_1!\cdot \dots \cdot b_n!\cdot k_1\cdot \dots \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 mit gleicher Zyklenzahl. Beispielsweise ist die Stirling-Zahl $s_{5,2}=30+20=50$, siehe die zweit- und drittletzte Zeile in der Tabelle.

Zykelklassen

Die Permutationen gleichen Zykeltyps bilden Äquivalenzklassen und man schreibt $\pi \sim \sigma$, wenn zwei Permutationen $\pi ,\sigma \in S_n$ den gleichen Typ besitzen, das heißt

$\pi \sim \sigma \iff \mathrm{typ}(\pi )=\mathrm{typ}(\sigma )$.

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 einer Komposition weist also unabhängig von der Reihenfolge der Operanden den gleichen Zykeltyp auf. Auch durch Konjugation mit einer beliebigen Permutation $\sigma$ ändert sich der Typ einer Permutation $\pi$ nicht, das heißt, es gilt

$\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 Zykeltyps bilden daher die Konjugationsklassen der symmetrischen Gruppe $S_n$.

Siehe auch

• Young-Tableau
• Zyklenzeiger

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur

Weblinks

• Vorlage:PlanetMath