Lemma von Burnside – Wikipedia
Das Lemma von Burnside drückt die Anzahl der Orbits einer (meist) endlichen Gruppe , die auf einer Menge 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.[1][2] Das Lemma war aber schon Augustin Louis Cauchy (1845)[3] 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 eine endliche Gruppe, die auf einer Menge operiert, die Menge der Fixpunkte in unter dem Gruppenelement (). Dann gilt für die Anzahl der Orbits (Bahnen von Punkten, die bei Wirkung von auf auseinander hervorgehen) der Wirkung von auf :
- .
Die Bezeichnung Lemma von Burnside ist nicht ganz eindeutig.
Der Beweis beruht auf der Identität
- ,
wobei die Stabilisator-Untergruppe zu ist (). Das Lemma folgt durch Anwendung der Bahnformel mit Berücksichtigung der Tatsache, dass die disjunkte Vereinigung der Orbits ist.
Beispiel
[Bearbeiten | Quelltext bearbeiten]Ein Kubus sei mit drei Farben in den Seitenflächen gefärbt, so dass die Menge der Seitenfärbungen ist (mit Elementen). Auf dieser Menge operiert die Drehgruppe des Kubus mit ihren 24 Elementen (Drehungen). Jede Drehung bewirkt eine Permutation der Menge .
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Face_colored_cube.png/220px-Face_colored_cube.png)
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 Elemente von unverändert.
- Es gibt sechs Drehungen jeweils einer Seite um 90 Grad, die jeweils Elemente unverändert lassen.
- Es gibt drei 180-Grad-Drehungen der Seiten, die jeweils Elemente unverändert lassen.
- Es gibt acht 120-Grad-Drehungen mit der Drehachse durch Eckpunkte mit jeweils Fixpunkten.
- Es gibt sechs 180-Grad-Drehungen mit der Drehachse durch Kanten, mit Fixpunkten.
Damit ergibt sich nach dem Lemma von Burnside für die Anzahl der Orbits:
Allgemein gilt bei Farben:
Literatur
[Bearbeiten | Quelltext bearbeiten]- 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
[Bearbeiten | Quelltext bearbeiten]- Burnside's Lemma, Art of Problem Solving
- Cauchy-Frobenius-Lemma, Mathworld (Eric Weisstein)
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ Frobenius, Über die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul, J. reine angew. Math., Band 101, 1887, S. 273–299
- ↑ Burnside veröffentlichte es auch in On Some Properties of Groups of Odd Order, Proc. London Math. Soc., Band 33, 1900, S. 162–184
- ↑ Cauchy, Comptes Rendus Acad. Sci. Paris, Band 21, 1845, S. 835, und in Œuvres Complètes d'Augustin Cauchy, Band 9, Gauthier-Villars 1896, S. 342–360