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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} eine endliche Gruppe, die als Permutationsgruppe auf einer Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Elementen operiert (siehe Gruppenwirkung). Als Permutationsgruppe hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g \in G} eine eindeutige Zerlegung in Zyklen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n= 1 \cdot b_1 + 2 \cdot b_2 + 3 \cdot b_3+ \cdots } ,

also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_1} 1-Zyklen (Fixpunkte), Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_2} 2-Zyklen usw. Der Zyklenindex von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist das Polynom (Zyklenindex, Zyklenzeiger):

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} mit einer endlichen Anzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y=|Y|} von Farben aus der Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Y} gefärbt. Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F=Y^X} die Menge dieser Färbungen (also Abbildungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f\colon X \to Y} ). Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} induziert eine Abbildung im Raum der Färbungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F} (über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F} ).

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w\colon F \to \mathbb Q }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} .

Der Satz von Pólya besagt nun, dass

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |M|=|Y^X/G| = \frac{1}{|G|}\sum_{g \in G} y^{b(g)}}

mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b(g)=\sum_i b_i (g)} der Summe der Zyklen und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(t) = f_0 + f_1 t + f_2 t^2 + \cdots}

mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_k} der Anzahl der Beiträge zur Farbe mit Gewicht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} (gedacht wird hierbei zum Beispiel an die Färbung von Knoten oder Kanten in einem Graph). Andererseits hat man die erzeugende Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F} , deren Koeffizienten die Anzahl der Muster zum jeweiligen Gewicht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} sind. Setzt man nun Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(t)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{f \in F} w(f)} ein und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(t) } für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{m \in M} w(m)} , so besagt der Satz von Pólya:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(t) = Z_G(f(t),f(t^2),f(t^3),\ldots,f(t^n))}

oder bei Verwendung mehrerer Variabler:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Y=\{b,w\}} . Die Symmetriegruppe G ist die Gruppe der Permutationen von m Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z_G(t_1,t_2,t_3) = \frac{1}{6}\left(t_1^3 + 3 t_1 t_2 + 2 t_3\right)}

Es ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(t)=1+t} . Die erzeugende Funktion ist: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z_G(t_1,t_2,t_3,t_4) = \frac{1}{24}\left(t_1^6 + 9 t_1^2 t_2^2 + 8 t_3^2 + 6 t_2 t_4\right)}

Die erzeugende Funktion ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 + 2 t^4 + 3 t^3 + 2 t^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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z_R(t_1,t_2,t_3,t_4) = \frac{1}{24}\left(t_1^6 + 6 t_1^2 t_4 + 3 t_1^2 t_2^2 + 8 t_3^2 + 6 t_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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(t)=Z_R(t,t,t,t) = \frac{1}{24}\left(t^6+ 3t^4 + 12 t^3 + 8 t^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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_3} die die Kinder jedes Knotens permutiert.

Der Zeigerindex der symmetrischen Gruppe mit 3 Elementen ist:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z_{S_3}(t_1,t_2,t_3) = \frac{t_1^3 + 3 t_1 t_2 + 2 t_3}{6}.}

Die Gewichte sind die Anzahl der Knoten, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(t) = 1+ F_1 t+ F_2 t^2+ F_3 t^3+ \cdots} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F_k} der Anzahl der Bäume mit k Knoten, und der Satz von Pólya ergibt die Rekursionsrelation:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(t) = 1 + t\frac{F(t)^3 + 3 F(t)F(t^2) + 2 F(t^3)}{6}}

dabei wurde Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t_i=t^i} gesetzt (mit der Knotenzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F_n} von ternären Wurzelbäumen mit n Knoten:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F_0 = 1}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F_n} sind

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 (online [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; abgerufen am 13. Juli 2019]). 
• Frank Harary, Edgar M. Palmer: Graphical Enumeration, Elsevier 2014

Weblinks

• Pólya Enumeration Theorem, Mathworld