Abzählsatz von Pólya

mathematischer Satz

Der Abzählsatz von Pólya aus der enumerativen Kombinatorik und Gruppentheorie erlaubt die Abzählung zum Beispiel von Bäumen, einfachen Graphen (mit Anwendung auf chemische Verbindungen) und von Gruppen endlicher Ordnung. Gemeinsam ist diesen Abzählproblemen die Symmetrie bezüglich der Operation einer endlichen Gruppe auf einer Menge. Der Satz wurde von George Pólya 1937 bewiesen (und wie sich später zeigte vorher von J. Howard Redfield) und erweitert das Lemma von Burnside.

Der Abzählsatz ist Teil einer ganzen Theorie, die Pólya dazu entwickelte, und benutzt wie viele Ansätze in der enumerativen Kombinatorik die Methode erzeugender Polynome und Potenzreihen.

Formulierung

Bearbeiten

Sei   eine endliche Gruppe, die als Permutationsgruppe auf einer Menge   mit   Elementen operiert (siehe Gruppenwirkung). Als Permutationsgruppe hat   für jedes   eine eindeutige Zerlegung in Zyklen:

 ,

also   1-Zyklen (Fixpunkte),   2-Zyklen usw. Der Zyklenindex von   ist das Polynom (Zyklenindex, Zyklenzeiger):

 

Bei endlichen Mengen brechen die Produkte beim n-Zyklus ab und man hat ein Polynom.

Gleichzeitig seien die Elemente von   mit einer endlichen Anzahl   von Farben aus der Menge   gefärbt. Es sei   die Menge dieser Färbungen (also Abbildungen  ).   induziert eine Abbildung im Raum der Färbungen   (über  ) und liefert dann auch Äquivalenzklassen auf den Färbungen, sogenannte Muster (entsprechend Orbits oder Bahnen von   in  ).

Den Färbungen wird in der allgemeinen Fassung des Satzes noch ein Gewicht zugewiesen, mit Werten in den rationalen Zahlen:

 
 .

Das Gewicht ist auf jedem Muster konstant, man hat also eine Gewichtsverteilung auf der Menge der Muster  .

Der Satz von Pólya besagt nun, dass

 

Die Formel drückt die Summe der Gewichte über alle Muster als Wert des Zyklenzeigers aus. Im einfachsten Fall des Gewichts 1 für alle Muster erhält man auf der linken Seite die Anzahl der Muster:

 

mit   der Summe der Zyklen und   der Anzahl der Farben. Das folgt auch unmittelbar aus dem Lemma von Burnside und kann als die einfachste Version des Satzes von Pólya betrachtet werden (ohne Gewichte).

Eine andere Formulierung vergleicht die Koeffizienten in zwei erzeugenden Funktionen. Zum einen hat man die erzeugende Funktion der Farben

 

mit   der Anzahl der Beiträge zur Farbe mit Gewicht   (gedacht wird hierbei zum Beispiel an die Färbung von Knoten oder Kanten in einem Graph). Andererseits hat man die erzeugende Funktion  , deren Koeffizienten die Anzahl der Muster zum jeweiligen Gewicht   sind. Setzt man nun   für   ein und   für  , so besagt der Satz von Pólya:

 

oder bei Verwendung mehrerer Variabler:

 .

Beispiel: Graphen mit 3 und 4 Knoten

Bearbeiten

Bei einem Graph mit m Knoten, also   möglichen Kanten, wird eine Färbung mit zwei Farben auf dem Raum X möglicher Kanten mit zwei Farben eingeführt: schwarz (b) falls die Kante im Graph vorhanden ist und weiß (w) wenn nicht, also  . Die Symmetriegruppe G ist die Gruppe der Permutationen von m Knoten   (symmetrische Gruppe der Ordnung m).

Der Abzählsatz von Pólya liefert die Anzahl der nichtisomorphen Graphen. Eine Isomorphieklasse entspricht einem Orbit von G auf der Menge  . Das Gewicht entspricht der Anzahl der Kanten im Graph. Bei drei Knoten gibt es acht Graphen die in vier Isomorphieklassen zerfallen.

Der Zeigerindex ist:

 

Es ist  . Die erzeugende Funktion ist:   was vier Isomorphieklassen ergibt jeweils mit 0, 1, 2 und 3 Kanten.

Bei vier Knoten mit sechs möglichen Kanten hat man die symmetrische Gruppe der Ordnung vier und der Zeigerindex ist:

 

Die erzeugende Funktion ist

 

Daraus kann man die Anzahl der Graphen mit bestimmter Kantenzahl direkt ablesen. Es gibt 11 Isormorphieklassen, jeweils eine mit Kantenanzahl k=0,1,5,6, jeweils zwei mit Kantenzahl k=2 und k=4, drei mit k=3.

Beispiel: Gefärbter Kubus

Bearbeiten

Die sechs Seiten eines Kubus seien mit t Farben gefärbt. Die Symmetriegruppe G ist hier die Rotationsgruppe R, deren 24 Elemente im Artikel Lemma von Burnside aufgeführt sind. Der Zeigerindex ist:

 

Benutzt man die Version des Abzählsatzes ohne Gewicht (oder anders ausgedrückt mit Gewicht 0 für jede Farbe) erhält man:

 

für die Anzahl der bezüglich R nicht äquivalenten Färbungen, abhängig von der Zahl der Farben t.

Beispiel: Ternäre Wurzelbäume

Bearbeiten

Betrachten werden Bäume mit ausgezeichneter Wurzel und maximal drei Kanten (Ästen) pro Knoten. Man kann sie auch betrachten als bestehend aus Knoten mit genau drei Ästen, wobei einige Äste nicht auf weitere innere Knoten, sondern auf Blätter weisen, also nicht weiterführen. Die Unterbäume, die an einem Knoten ansetzen, sind dessen Kinder. Ein Wurzelbaum lässt sich rekursiv aufbauen, da die Kinder ebenfalls ternäre Wurzelbäume sind. Die Symmetriegruppe G ist die symmetrische Gruppe   die die Kinder jedes Knotens permutiert.

Der Zeigerindex der symmetrischen Gruppe mit 3 Elementen ist:

 

Die Gewichte sind die Anzahl der Knoten,   mit   der Anzahl der Bäume mit k Knoten, und der Satz von Pólya ergibt die Rekursionsrelation:

 

dabei wurde   gesetzt (mit der Knotenzahl   als Gewicht), ein Faktor t kommt im zweiten Term der rechten Seite ins Spiel weil die Wurzel nicht mitgerechnet wurde, diese wird außerdem durch Addition der Eins berücksichtigt.

Diese ist wiederum äquivalent zur folgenden Rekursionsrelation für die Anzahl   von ternären Wurzelbäumen mit n Knoten:

 
 

(a,b,c, sind nicht-negative ganze Zahlen).

Die ersten Werte von   sind[1]

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241

Also jeweils einer mit n=0,1,2 Knoten, 2 mit n=3 Knoten, 4 mit n=4 Knoten usw.

Literatur

Bearbeiten
  • George Pólya: Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. In: Acta mathematica. Band 68, Nr. 1, 1937, S. 145–254 (projecteuclid.org [abgerufen am 13. Juli 2019]).
    • eine englische Ausgabe mit R. C. Read erschien bei Springer 1987: Combinatorial enumeration of groups, graphs, and chemical compounds
  • Nicolaas Govert de Bruijn: Pólyas Abzähl-Theorie, Muster für Graphen und chemische Verbindungen. In: Konrad Jacobs (Hrsg.): Selecta mathematica III (= Heidelberger Taschenbücher. Band 86). Springer, Berlin, Heidelberg, New York 1971, ISBN 3-540-05333-6, S. 1–26 (tue.nl [PDF; 1,1 MB; abgerufen am 13. Juli 2019]).
  • Frank Harary, Edgar M. Palmer: Graphical Enumeration. Elsevier, 2014.
Bearbeiten

Einzelnachweise

Bearbeiten
  1. OEIS A000598