Zyklenzeiger

Der Zyklenzeiger, auch Zyklenindikator genannt, wird in der Mathematik als Hilfsmittel eingesetzt, wenn bei der Bestimmungen komplexerer Anzahlen in der Kombinatorik Symmetrien berücksichtigt werden können.

Konkret ist der Zyklenzeiger ein Polynom, welches Informationen über die Struktur einer passenden Gruppe abstrahiert.

Die bekannteste Anwendung ist der Satz von Pólya, welcher das Abzählen komplexerer Äquivalenzklassen von Objekten ermöglicht, etwa die Anzahl aller echt unterschiedlichen Moleküle einer Familie in der Chemie oder die der Bäume in der Graphentheorie.

Formale Definition

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} eine Permutationsgruppe mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} Elementen vom Grad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} . Jede Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma \in G} lässt sich eindeutig als Vereinigung disjunkter Zyklen darstellen. Der Zyklentyp der Permutation sei durch die Anzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j_k(\sigma)} aller Zyklen von $\sigma$ mit Länge $k$ gegeben, also

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

Nun wird jedem $\sigma \in G$ ein Monom

$M(\sigma ):=a_{1}^{j_{1}(\sigma )}\cdot a_{2}^{j_{2}(\sigma )}\cdot \cdots \cdot a_{n}^{j_{n}(\sigma )}=\prod _{k=1}^{n}a_{k}^{j_{k}(\sigma )}$

in den Variablen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_1, a_2, \ldots, a_n} zugewiesen. Dann ist der Zyklenzeiger von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} gegeben durch das den Durchschnitt bildende Polynom

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z(G) := Z(G; a_1, a_2, \ldots a_n) := \frac{1}{|G|} \sum_{\sigma \in G} M(\sigma) = \frac{1}{m} \sum_{\sigma \in G} \prod_{k=1}^n a_k^{j_k(\sigma)}} .

Beispiele

Zyklische Gruppe C₃

Die zyklische Gruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C_3 = \lbrace a^0,\, a^1,\, a^2 \rbrace} wird durch die drei Permutationen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} a^0 = \sigma_1 = [1 2 3] &= (1)(2)(3)\\ a^1 = \sigma_2 = [2 3 1] &= (1 2 3)\\ a^2 = \sigma_3 = [3 1 2] &= (1 3 2) \end{align}}

realisiert. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma_1} besteht aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3} Zyklen der Länge Eins, also lautet das entsprechende Monom $a_{1}^{3}$. Hingegen bestehen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma_2} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma_3} jeweils aus einem Zyklus der Länge 3, also ergibt sich zweimal das Monom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_3^1} . Durchschnittsbildung führt auf den Zyklenzeiger von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C_3} :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z(C_3) = \frac{1}{3} \left( a_1^3 + 2 a_3 \right)} .

Symmetrische Gruppe S₃

Die symmetrische Gruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_3} besteht aus den sechs Permutationen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \sigma_1 = [1 2 3] &= (1)(2)(3)\\ \sigma_2 = [1 3 2] &= (1)(2 3)\\ \sigma_3 = [2 1 3] &= (1 2)(3)\\ \sigma_4 = [2 3 1] &= (1 2 3)\\ \sigma_5 = [3 1 2] &= (1 3 2)\\ \sigma_6 = [3 2 1] &= (1 3)(2) \end{align} }

und der Zyklenzeiger ist

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

Drehgruppe eines Würfels

Datei:Face colored cube.png

Würfel mit eingefärbten Seiten

Die Drehgruppe eines Würfels, das heißt die Automorphismengruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} seiner Rotationen im dreidimensionalen Raum, kann als Permutationsgruppe der sechs Seiten des Würfels dargestellt werden. Insgesamt gibt es 24 verschiedene Automorphismen, die für die Berechnung des Zyklenzeigers dieser Gruppe klassifiziert werden müssen:

• Eine Rotation um 0°: Dies ist die Identität, die das Monom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_1^6} beiträgt.

• Sechs Rotationen der Seiten um 90°: Es gibt drei 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 jeweils durch einen Zyklus der Länge 4 parallel zur Rotationsachse permutiert werden. Damit ergibt sich das Monom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3 \cdot 2 \cdot a_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 2 entstehen. Damit ergibt sich das Monom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3 \cdot a_1^2 a_2^2} .

• Acht Rotationen der Ecken um 120°: Die vier Rotationsachsen gehen hier durch zwei entgegengesetzte Punkte, d. h. die Endpunkte einer Hauptdiagonale. Es entstehen jeweils zwei Zyklen der Länge 3 der Oberflächen, die an die Endpunkte angrenzen. Damit ergibt sich das Monom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 4 \cdot 2 \cdot a_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 2 und es ergibt sich somit das Monom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 6 \cdot a_2^3} .

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z(G) = \frac{1}{24} \left( a_1^6 + 6 a_1^2 a_4 + 3 a_1^2 a_2^2 + 8 a_3^2 + 6 a_2^3 \right).}

Diese Formel kann jetzt für verschiedene kombinatorische Probleme verwendet werden: Die Substitution $a_{1}:=a_{2}:=a_{3}:=a_{4}:=n$ und Anwendung des Satzes von Pólya ergibt etwa, dass es insgesamt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} verschiedenen Farben einzufärben.

Man beachte: Alternativ hätte man auch eine auf die Ecken oder Kanten (wenn der Würfel als Graph aufgefasst wird) wirkende Gruppe betrachten können, was allerdings auf andere Zyklenzeiger führen würde.

Weblinks

• Nicolaas Govert de Bruijn: Pólyas Abzähl-Theorie: Muster für Graphen und chemische Verbindungen. (PDF; 1 MB; 26 Seiten) – Eine ausführliche und lesenswerte Einführung, bei der die Beweise durch konkrete Beispiele motiviert werden. Auch erschienen in: Konrad Jacobs (Hrsg.): Selecta Mathematica III. Springer, Berlin 1971, ISBN 3-540-05333-6 (Heidelberger Taschenbücher).
• William May: Introduction to Pólya Enumeration Theory. (PDF; 1,4 MB; 41 Folien)
• Harald Fripertinger: Zyklenzeiger linearer Gruppen und Abzählung linearer Codes. (PDF; 180 kB; 13 Seiten)
• Marko Riedel: Pólya’s enumeration theorem and the symbolic method. (PDF; 181 kB; 14 Seiten) – Enthält insbesondere Formeln für Zyklenzeiger mehrerer elementarer Gruppen.

Literatur

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