Zyklenzeiger

Diese Baustelle befindet sich fälschlicherweise im Artikelnamensraum. Bitte verschiebe die Seite oder entferne den Baustein {{Baustelle}}.

Der Zyklenzeiger ist ein {tolles Hilfsmittel}.

Formale Definition

Sei $G$ eine Permutationsgruppe mit $m$ Elementen und Grad $n$ . Jede Permutation $\sigma \in G$ lässt sich eindeutig als Vereinigung disjunkter Zyklen darstellen. Nun bezeichne $|c|$ die Länge eines Zyklus $c$ und $j_{k}(\sigma )$ die Anzahl aller Zyklen von $\sigma$ mit Länge k, also

0\leq j_{k}(\sigma )\leq \lfloor n/k\rfloor {\text{ und }}\sum _{k=1}^{n}k\,j_{k}(\sigma )\;=n.

Nun wird $\sigma$ das Monom

\prod _{c\in \sigma }a_{|c|}=\prod _{k=1}^{n}a_{k}^{j_{k}(g)}

in den formalen Variablen $a_{1},a_{2},\ldots ,a_{n}$ zugewiesen. Dann ist der Zyklenzeiger von $G$ gegeben durch

Z(G)={\frac {1}{|G|}}\sum _{\sigma \in G}\prod _{k=1}^{n}a_{k}^{j_{k}(g)}.

Beispiele

Zyklische Gruppe $C_{3}$

Die zyklische Gruppe $C_{3}=\lbrace a^{0},\,a^{1},\,a^{2}\rbrace$ ist isomorph zu den drei Permutationen

{\begin{aligned}a^{0}=\sigma _{1}=[123]&=(1)(2)(3)\\a^{1}=\sigma _{2}=[231]&=(123)\\a^{2}=\sigma _{3}=[312]&=(132)\\\end{aligned}}

$\sigma _{1}$ besteht aus $3$ Zyklen der Länge Eins, also lautet das entsprechende Monom $a_{1}^{3}$ . Hingegen bestehen $\sigma _{2}$ und $\sigma _{3}$ jeweils aus einem Zyklus der Länge 3, also ergibt sich zweimal das Monom $a_{3}^{1}$ .

Der Zyklenzeiger ist quasi der Durchschnitt der drei Monome:

Z(C_{3})={\frac {1}{3}}\left(a_{1}^{3}+2a_{3}\right).

Die Punktgruppe eines Würfels

Würfel mit eingefärbten Seiten

Die Punktgruppe eines Würfels, d. h. die Automorphismengruppe $G$ seiner Rotationen im dreidimensionalen Raum, kann als Permutationsgruppe der sechs Seiten des Würfels (oder genauso gut seiner Ecken oder Kanten, wenn der Würfel als Graph aufgefasst wird) dargestellt werden. Insgesamt gibt es 24 verschiedene Automorphismen, die für die Berechnung des Zyklenzeigers klassifiziert werden müssen:

Die Identität ist eindeutig und trägt das Monom

a_{1}^{6}

bei.

Sechs Rotationen der Seiten um 90°: Es gibt sechs Möglichkeiten, die Rotationsachse durch den Mittelpunkt einer Seite und dem auf der gegenüberliegenden Seite zu legen. Diese beiden Seiten bleiben also durch die Rotation unverändert, wogegen die anderen vier Seiten durch einen Zyklus der Länge 4 paralell zur Rotationsachse permutiert werden. Damit ergibt sich das Monom

6a_{1}^{2}a_{4}

.

Drei Rotationen der Seiten um 180°: Es wird um dieselbe Achse wie eben rotiert. Diesmal werden jedoch gegenüberliegende Seiten vertauscht, so dass zwei Zyklen der Länge Zwei entstehen. Damit ergibt sich das Monom

3a_{1}^{2}a_{2}^{2}

.

Acht Rotationen der Ecken um 120°: Die Rotationsachse geht hier durch zwei entgegengesetzte Punkte (die Endpunkte einer Hauptdiagonale). Es entstehen zwei Zyklen der Länge 3 jeweils der Oberflächen, die an die Endpunkte angrenzen. Damit ergibt sich das Monom

8a_{3}^{2}.

.

Sechs Rotationen der Kanten um 180°:

Insgesamt ergibt sich damit für den Zyklenzeiger der Gruppe G

Z(G)={\frac {1}{24}}\left(a_{1}^{6}+6a_{1}^{2}a_{4}+3a_{1}^{2}a_{2}^{2}+8a_{3}^{2}+6a_{2}^{3}\right).

Diese Formel kann jetzt für verschiedene kombinatorische Probleme verwendet werden: Die Substitution $a_{1}:=a_{2}:=n$ und Anwendung von Burnsides Lemma ergibt etwa, dass es insgesamt

{\frac {1}{24}}\left(n^{6}+3n^{4}+12n^{3}+8n^{2}\right)

verschiedene echte (d. h. durch Rotation nicht ineinander überführbare) Möglichkeiten gibt, die Seiten eines Würfels mit $n$ verschiedenenen Farben einzufärben.

Kategorie:Gruppentheorie Kategorie:Kombinatorik