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 $π \in S_{n}$ , dann ist der Zykeltyp dieser Permutation der formale Ausdruck

typ (π) = 1^{b_{1}} 2^{b_{2}} \dots n^{b_{n}}

,

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

typ (π) = (k_{1}, k_{2}, \dots, k_{s})

,

wobei $s \leq n$ und $k_{1} \geq \dots \geq k_{s} \in ℕ$ die Längen der Zyklen in der Zykeldarstellung der Permutation in absteigender Reihenfolge sind.^[3]^[4] Gelegentlich werden die Zyklenlängen auch in aufsteigender Reihenfolge notiert.^[5] 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

π = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 4 & 1 & 3 & 5 & 7 & 6 \end{matrix}) = (1243) (5) (67) \in S_{7}

weist den Zykeltyp

typ (π) = 1^{1} 2^{1} 3^{0} 4^{1} 5^{0} 6^{0} 7^{0} = 1^{1} 2^{1} 4^{1}

oder

typ (π) = (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 $π = (1457) (36) (2) \in S_{7}$ .

Allgemeinere Beispiele

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

identische Permutation:

typ (π) = 1^{n}

oder

typ (π) = (1, \dots, 1)

Transpositionen (Vertauschungen):

typ (π) = 1^{n - 2} 2^{1}

oder

typ (π) = (2, 1, \dots, 1)

zyklische Permutationen der Länge $r \geq 2$ :

typ (π) = 1^{n - r} r^{1}

oder

typ (π) = (r, 1, \dots, 1)

fixpunktfreie Permutationen:

typ (π) = 2^{b_{2}} \dots n^{b_{n}}

oder

typ (π) = (k_{1}, \dots, k_{s})

mit

k_{j} \geq 2

für alle

j

selbstinverse Permutationen:

typ (π) = 1^{b_{1}} 2^{b_{2}}

oder

typ (π) = (k_{1}, \dots, k_{s})

mit

k_{j} \leq 2

für alle

j

Anzahlen

$n$	Zykeltyp		Zykelstruktur	Anzahl
1	1¹	(1)	( • )	1
2	1²	(1,1)	( • ) ( • )	1
2	2¹	(2)	( • • )	1
3	1³	(1,1,1)	( • ) ( • ) ( • )	1
	1¹ 2¹	(2,1)	( • • ) ( • )	3
	3¹	(3)	( • • • )	2
4	1⁴	(1,1,1,1)	( • ) ( • ) ( • ) ( • )	1
	1² 2¹	(2,1,1)	( • • ) ( • ) ( • )	6
	2²	(2,2)	( • • ) ( • • )	3
	1¹ 3¹	(3,1)	( • • • ) ( • )	8
	4¹	(4)	( • • • • )	6
5	1⁵	(1,1,1,1,1)	( • ) ( • ) ( • ) ( • ) ( • )	1
	1³ 2¹	(2,1,1,1)	( • • ) ( • ) ( • ) ( • )	10
	1¹ 2²	(2,2,1)	( • • ) ( • • ) ( • )	15
	1² 3¹	(3,1,1)	( • • • ) ( • ) ( • )	20
	2¹ 3¹	(3,2)	( • • • ) ( • • )	20
	1¹ 4¹	(4,1)	( • • • • ) ( • )	30
	5¹	(5)	( • • • • • )	24

Zahl der Typen

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

1 \cdot b_{1} + 2 \cdot b_{2} + \dots + 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 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$ ,^[4] die durch die Folge

1, 2, 3, 5, 7, 11, \dots

(Folge A000041 in 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 $π \in S_{n}$ mit $typ (π) = 1^{b_{1}} 2^{b_{2}} \dots n^{b_{n}}$ beträgt^[6]

\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}}}

(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 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.^[6] 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 $π \sim σ$ , wenn zwei Permutationen $π, σ \in S_{n}$ den gleichen Typ besitzen, das heißt

π \sim σ \Leftrightarrow typ (π) = typ (σ)

.

Für die inverse Permutation $π^{- 1}$ einer Permutation $π$ gilt immer

π^{- 1} \sim π

,

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

π \circ σ \sim σ \circ π

,

das Resultat einer Komposition weist also unabhängig von der Reihenfolge der Operanden den gleichen Zykeltyp auf. Auch durch Konjugation mit einer beliebigen Permutation $σ$ ändert sich der Typ einer Permutation $π$ nicht, das heißt, es gilt

σ \circ π \circ σ^{- 1} \sim π

.

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

Siehe auch

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.

Weblinks

Roger Lipsett: Conjugacy classes in the symmetric group Sⁿ. In: PlanetMath. (englisch)

Einzelnachweise

1 2 Aigner: Diskrete Mathematik. S. 11.
↑ Reiss, Stroth: Endliche Strukturen. S. 171.
↑ Artin: Algebra. S. 241.
1 2 3 Kurzweil, Stellmacher: Theorie der endlichen Gruppen: eine Einführung. S. 80.
↑ Jacobs, Jungnickel: Einführung in die Kombinatorik. S. 293.
1 2 Aigner: Diskrete Mathematik. S. 12.
↑ Artin: Algebra. S. 242.

[aigner11-1] 1 2 Aigner: Diskrete Mathematik. S. 11.

[2] Reiss, Stroth: Endliche Strukturen. S. 171.

[3] Artin: Algebra. S. 241.

[kurzweil-4] 1 2 3 Kurzweil, Stellmacher: Theorie der endlichen Gruppen: eine Einführung. S. 80.

[5] Jacobs, Jungnickel: Einführung in die Kombinatorik. S. 293.

[aigner12-6] 1 2 Aigner: Diskrete Mathematik. S. 12.

[7] Artin: Algebra. S. 242.

[1]

[2]

[3]

[4]

[5]

[6]

[7]