Lemma von Burnside

Das Lemma von Burnside drückt die Anzahl der Orbits einer (meist) endlichen Gruppe $G$, die auf einer Menge $X$ wirkt (siehe Gruppenwirkung), durch ein Mittel über die Fixpunkte zu den einzelnen Gruppenelementen aus.

Die Benennung nach William Burnside ist eigentlich falsch, er erwähnt den Satz in seinem Buch On the theory of groups of finite order von 1897, schreibt ihn dort aber Ferdinand Georg Frobenius (1887) zu. Das Lemma war aber schon Augustin Louis Cauchy (1845) bekannt und heißt deshalb manchmal auch Cauchy-Frobenius-Lemma. Auch die Bezeichnung Abzählsatz von Burnside ist verbreitet, da er eine Vorstufe des Abzählsatzes von Pólya (1937) ist, eine Verfeinerung und Erweiterung des Lemmas von Burnside.

Sei $G$ eine endliche Gruppe, die auf einer Menge $X$ operiert, $X^{g}$ die Menge der Fixpunkte in $X$ unter dem Gruppenelement $g\in G$ ($X^{g}=\{x\in X:gx=x\}$). Dann gilt für die Anzahl $|X/G|$ der Orbits (Bahnen von Punkten, die bei Wirkung von $G$ auf $X$ auseinander hervorgehen) der Wirkung von $G$ auf $X$:

$|X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|$.

Die Bezeichnung Lemma von Burnside ist nicht ganz eindeutig.

Der Beweis beruht auf der Identität

$\sum _{g\in G}|X^{g}|=|\{(g,x)\in G\times X\mid g\cdot x=x\}|=\sum _{x\in X}|G_{x}|$,

wobei $G_{x}$ die Stabilisator-Untergruppe zu $x$ ist ($G_{x}=\{g\in G:gx=x\}$). Das Lemma folgt durch Anwendung der Bahnformel mit Berücksichtigung der Tatsache, dass $X$ die disjunkte Vereinigung der Orbits ist.

Beispiel

Ein Kubus sei mit drei Farben in den Seitenflächen gefärbt, so dass $X$ die Menge der Seitenfärbungen ist (mit $3^{6}$ Elementen). Auf dieser Menge $X$ operiert die Drehgruppe des Kubus mit ihren 24 Elementen (Drehungen). Jede Drehung bewirkt eine Permutation der Menge $X$.

Gesucht wird die Anzahl wesentlich verschiedener Färbungen bezüglich der Drehsymmetrie des Kubus. Zwei Färbungen gelten in diesem Sinne als wesentlich verschieden, wenn sie nicht drehsymmetrisch zueinander sind, die eine also nicht durch eine Drehung des Kubus aus der anderen entstehen kann. Färbungen, die drehsymmetrisch zueinander sind, liegen im gleichen Orbit bezüglich der Drehgruppe und gelten als identisch im Sinne der Drehsymmetrie. Die Zahl der Orbits entspricht der Zahl der wesentlich verschiedenen Färbungen.

Kubus mit Seitenfärbung

Nach dem Lemma von Burnside lässt sich die Anzahl der Orbits durch die Anzahl der Fixpunkte der Elemente der Drehgruppe ausdrücken:

• Die Identität lässt alle $3^{6}$ Elemente von $X$ unverändert.
• Es gibt sechs Drehungen jeweils einer Seite um 90 Grad, die jeweils $3^{3}$ Elemente unverändert lassen.
• Es gibt drei 180-Grad-Drehungen der Seiten, die jeweils $3^{4}$ Elemente unverändert lassen.
• Es gibt acht 120-Grad-Drehungen mit der Drehachse durch Eckpunkte mit jeweils $3^{2}$ Fixpunkten.
• Es gibt sechs 180-Grad-Drehungen mit der Drehachse durch Kanten, mit $3^{3}$ Fixpunkten.

Damit ergibt sich nach dem Lemma von Burnside für die Anzahl der Orbits:

${\frac {1}{24}}\left(3^{6}+6\cdot 3^{3}+3\cdot 3^{4}+8\cdot 3^{2}+6\cdot 3^{3}\right)=57.$

Allgemein gilt bei $n$ Farben:

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

Literatur

• Peter M. Neumann: A lemma that is not Burnside's, The Mathematical Scientist, Band 4, 1979, S. 133–141.
• Frank Harary, E. M. Palmer: Graphical Enumeration, Academic Press 1973
• Joseph Rotman: An introduction to the theory of groups, Springer-Verlag, 1995

Weblinks

• Burnside's Lemma, Art of Problem Solving
• Cauchy-Frobenius-Lemma, Mathworld (Eric Weisstein)