Generierungsfunktionen

Generierungsfunktionen sind formale Potenzreihen, die eine Folge (a_n) durch Koeffizienten repräsentieren. Die häufigste Form ist die gewöhnliche Generierungsfunktion G(x) = sum_{n>=0} a_n x^n. Für beschriftete Objekte verwendet man die exponentielle Generierungsfunktion A(x) = sum_{n>=0} a_n x^n / n!. In der Wahrscheinlichkeitstheorie tritt die Wahrscheinlichkeitsgenerierungsfunktion G_X(s) = E[s^X] auf.

Generierungsfunktionen dienen der kompakten Darstellung und Manipulation von Folgen. Grundoperationen haben kombinatorische Bedeutungen: Das Produkt zweier gewöhnlicher Generierungsfunktionen entspricht der Faltung der Koeffizienten (Kombination unabhängiger Bausteine), die Ableitung verschiebt Koeffizienten und die Koeffizientenextraktion [x^n]G(x) liefert a_n. Rekurrenzgleichungen lassen sich oft durch algebraische Gleichungen für Generierungsfunktionen lösen.

Man unterscheidet zwischen formalen Potenzreihen und analytischen Generierungsfunktionen. Bei analytischer Betrachtung wird die Konvergenz (Konvergenzradius) wichtig und erlaubt asymptotische Auswertungen, etwa durch Singuläritätenanalyse. Die Lagrange-Inversionsformel und Methoden der komplexen Analysis sind zentrale Werkzeuge zur Koeffizientenbestimmung.

Anwendungsgebiete sind kombinatorische Zählprobleme, Analyse von Algorithmen, Wahrscheinlichkeitsverteilungen und Statistik. In der Kombinatorik bilden Generierungsfunktionen die Grundlage der symbolischen und analytischen Kombinatorik, weil sie strukturierte Konstruktionen systematisch in algebraische und analytische Ausdrücke überführen.