Abzählsatz von Pólya

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

Sei ${\displaystyle G}$ eine endliche Gruppe, die als Permutationsgruppe auf einer Menge ${\displaystyle X}$ mit ${\displaystyle n}$ Elementen operiert (siehe Gruppenwirkung). Als Permutationsgruppe hat ${\displaystyle G}$ für jedes ${\displaystyle g\in G}$ eine eindeutige Zerlegung in Zyklen:

${\displaystyle n=1\cdot b_{1}+2\cdot b_{2}+3\cdot b_{3}+\cdots }$,

also ${\displaystyle b_{1}}$ 1-Zyklen (Fixpunkte), ${\displaystyle b_{2}}$ 2-Zyklen usw. Der Zyklenindex von ${\displaystyle G}$ ist das Polynom (Zyklenindex, Zyklenzeiger):

${\displaystyle Z_{G}(t_{1},t_{2},\dotsc )={\frac {1}{|G|}}\sum _{g\in G}t_{1}^{b_{1}(g)}\cdot t_{2}^{b_{2}(g)}\cdots }$

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

Gleichzeitig seien die Elemente von ${\displaystyle X}$ mit einer endlichen Anzahl ${\displaystyle y=|Y|}$ von Farben aus der Menge ${\displaystyle Y}$ gefärbt. Es sei ${\displaystyle F=Y^{X}}$ die Menge dieser Färbungen (also Abbildungen ${\displaystyle f\colon X\to Y}$). ${\displaystyle G}$ induziert eine Abbildung im Raum der Färbungen ${\displaystyle F}$ (über ${\displaystyle (g\circ f)(x)=f(g^{-1}(x))}$) und liefert dann auch Äquivalenzklassen auf den Färbungen, sogenannte Muster (entsprechend Orbits oder Bahnen von ${\displaystyle G}$ in ${\displaystyle F}$).

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

${\displaystyle w\colon F\to \mathbb {Q} }$

${\displaystyle w(f)=\prod _{x\in X}w(f(x))}$.

Das Gewicht ist auf jedem Muster konstant, man hat also eine Gewichtsverteilung auf der Menge der Muster ${\displaystyle M}$.

Der Satz von Pólya besagt nun, dass

${\displaystyle \sum _{m\in M}w(m)=Z_{G}(\sum _{f\in F}w(f),\sum _{f\in F}w^{2}(f),\cdots )}$

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:

${\displaystyle |M|=|Y^{X}/G|={\frac {1}{|G|}}\sum _{g\in G}y^{b(g)}}$

mit ${\displaystyle b(g)=\sum _{i}b_{i}(g)}$ der Summe der Zyklen und ${\displaystyle y}$ 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

${\displaystyle f(t)=f_{0}+f_{1}t+f_{2}t^{2}+\cdots }$

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

${\displaystyle F(t)=Z_{G}(f(t),f(t^{2}),f(t^{3}),\ldots ,f(t^{n}))}$

oder bei Verwendung mehrerer Variabler:

${\displaystyle F(t_{1},t_{2},\ldots )=Z_{G}(f(t_{1},t_{2},\ldots ),f(t_{1}^{2},t_{2}^{2},\ldots ),f(t_{1}^{3},t_{2}^{3},\ldots ),\ldots ,f(t_{1}^{n},t_{2}^{n},\ldots ))}$.

Beispiel: Graphen mit 3 und 4 Knoten

Bei einem Graph mit m Knoten, also ${\displaystyle {\binom {m}{2}}}$ 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 ${\displaystyle Y=\{b,w\}}$. Die Symmetriegruppe G ist die Gruppe der Permutationen von m Knoten ${\displaystyle S_{m}}$ (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 ${\displaystyle Y^{X}}$. Das Gewicht entspricht der Anzahl der Kanten im Graph. Bei drei Knoten gibt es acht Graphen die in vier Isomorphieklassen zerfallen.

Der Zeigerindex ist:

${\displaystyle Z_{G}(t_{1},t_{2},t_{3})={\frac {1}{6}}\left(t_{1}^{3}+3t_{1}t_{2}+2t_{3}\right)}$

Es ist ${\displaystyle f(t)=1+t}$. Die erzeugende Funktion ist: ${\displaystyle F(t)=Z_{G}(t+1,t^{2}+1,t^{3}+1)={\frac {1}{6}}\left((t+1)^{3}+3(t+1)(t^{2}+1)+2(t^{3}+1)\right)=F(t)=t^{3}+t^{2}+t+1}$ 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:

${\displaystyle Z_{G}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+9t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}t_{4}\right)}$

Die erzeugende Funktion ist

${\displaystyle F(t)=Z_{G}(t+1,t^{2}+1,t^{3}+1,t^{4}+1)={\frac {(t+1)^{6}+9(t+1)^{2}(t^{2}+1)^{2}+8(t^{3}+1)^{2}+6(t^{2}+1)(t^{4}+1)}{24}}=F(t)=t^{6}+t^{5}+2t^{4}+3t^{3}+2t^{2}+t+1}$

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

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:

${\displaystyle Z_{R}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+6t_{1}^{2}t_{4}+3t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}^{3}\right)}$

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

${\displaystyle F(t)=Z_{R}(t,t,t,t)={\frac {1}{24}}\left(t^{6}+3t^{4}+12t^{3}+8t^{2}\right)}$

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

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 ${\displaystyle S_{3}}$ die die Kinder jedes Knotens permutiert.

Der Zeigerindex der symmetrischen Gruppe mit 3 Elementen ist:

${\displaystyle Z_{S_{3}}(t_{1},t_{2},t_{3})={\frac {t_{1}^{3}+3t_{1}t_{2}+2t_{3}}{6}}.}$

Die Gewichte sind die Anzahl der Knoten, ${\displaystyle F(t)=1+F_{1}t+F_{2}t^{2}+F_{3}t^{3}+\cdots }$ mit ${\displaystyle F_{k}}$ der Anzahl der Bäume mit k Knoten, und der Satz von Pólya ergibt die Rekursionsrelation:

${\displaystyle F(t)=1+t{\frac {F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})}{6}}}$

dabei wurde ${\displaystyle t_{i}=t^{i}}$ gesetzt (mit der Knotenzahl ${\displaystyle i}$ 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 ${\displaystyle F_{n}}$ von ternären Wurzelbäumen mit n Knoten:

${\displaystyle F_{0}=1}$

${\displaystyle F_{n+1}={\frac {1}{6}}\left(\sum _{a+b+c=n}F_{a}F_{b}F_{c}+3\sum _{a+2b=n}F_{a}F_{b}+2\sum _{3a=n}F_{a}\right)}$

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

Die ersten Werte von ${\displaystyle F_{n}}$ 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

• 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. 

Weblinks

• Pólya Enumeration Theorem, Mathworld

Einzelnachweise

1. OEIS A000598