Zyklenzeiger

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

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit den Autoren auf.

Der Zyklenzeiger, auch Zyklenindikator genannt, 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, d. h. 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°: Die Rotationsachse geht hier durch die Mittelpunkte zweier diagonal gegenüberliegender Kanten. Es werden jeweils die beiden Seiten vertauscht, die an eine der beiden Kanten angrenzen, sowie die beiden Seiten, die jeweils nur an eine Ecke der beiden Kanten angrenzen. Insgesamt gibt es also drei Zyklen der Länge Zwei und es ergibt sich somit das Monom $6a_{2}^{3}$.

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)$

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

Siehe auch

• Burnsides Lemma
• Satz von Pólya

Weblinks

• Harald Fripertinger: Zyklenzeiger linearer Gruppen und Abzählung linearer Codes (englische Fassung: Cycle indices of linear, affine and projective groups)
• Marko Riedel: Pólya's enumeration theorem and the symbolic method

Literatur

• Martin Aigner: Diskrete Mathematik. Kapitel 4.4 Muster und Zyklenindikator, Vieweg+Teubner, 6. korr. Aufl. 2006, ISBN-13: 978-3-83480084-8
• Konrad Jacobs und Dieter Jungnickel: Einführung in die Kombinatorik. Kapitel ⅩⅠⅠⅠ Die Abzähltheorie von Pólya, de Gruyter Lehrbuch 2003, ISBN 978-3-11-019799-0.

Kategorie:Lineare Algebra Kategorie:Gruppentheorie Kategorie:Kombinatorik