Ein Theorem, das nichtäquivalente Färbungen oder kombinatorische Konfigurationen unter einer endlichen Permutationsgruppe zählt, indem man Zählvariablen für Farben in das Zyklusindex-Polynom der Gruppe einsetzt.

Prinzip

Kodiert die Zyklendekomposition jedes Gruppenelements in ein formales Monom (den Zyklusindex); ersetzt man die Variablen durch Summen oder Polynome, die Farbwahl repräsentieren, erhält man eine erzeugende Funktion, deren Koeffizienten die bis auf die Gruppenwirkung unterschiedlichen Konfigurationen zählen.

Demonstration

Um verschiedene Färbungen einer Halskette mit n Perlen unter Rotation zu zählen, berechne den Zyklusindex der Rotationsgruppe und setze x_k = Anzahl der Farboptionen für einen k-Zyklus ein; daraus folgt die Zahl der nichtäquivalenten Färbungen.

Fehlanwendung

Die Zyklusindex-Substitution mit Gewichtungen oder Abhängigkeiten der Farben verwenden, die die Annahme unabhängiger Farbzuweisung an Zykluspositionen verletzen, oder das Theorem anwenden, wenn die Wirkung Positionen auf nicht durch Zyklen erfasste Weise permutiert.

Konsequenz

Erzeugt geschlossene erzeugende Funktionen oder explizite Zählformeln für symmetrische kombinatorische Klassen, behandelt gewichtete Färbungen und Musterzählungen und verallgemeinert Burnsides Mittelung zu einem mächtigen algebraischen Werkzeug.

Umkehrung

Umgekehrt betrachtet liefert die Koeffizientenentwicklung des substituierten Zyklusindex die Fixpunktbeiträge der einzelnen Gruppenelemente — Burnside erscheint als Spezialfall von Pólya bei einfachen Substitutionen.

Abgrenzung

Erfordert eine endliche Permutationsgruppe, die auf einer endlichen Menge von Positionen wirkt, sowie die Unabhängigkeit der Farbwahl über Zyklen; kontinuierliche Symmetrien oder positionsabhängige Zwänge benötigen Modifikation.

Semantische Spannung

Spannung zwischen algebraischen Erzeugenden-Techniken (Zyklusindex) und konstruktiver kombinatorischer Klassifikation; Zyklusindex-Methoden ersetzen explizite Aufzählung durch algebraische Kodierung, was die kombinatorische Intuition teilweise verschleiern kann, aber breite Berechnungen ermöglicht.

Synthese

Pólyas Satz hebt Burnsides Mittelung in einen algebraischen Rahmen: Der Zyklusindex sammelt Zyklenstrukturen und Substitution übersetzt Farbwahl in eine erzeugende Funktion, die nichtäquivalente Konfigurationen zählt.