Generatorfunktion

Die Generatorfunktion, oft auch Erzeugungsfunktion genannt, ist ein Werkzeug der diskreten Mathematik zur Kodierung einer Zahlenfolge durch eine Potenzreihe. Für eine Folge a_n mit n≥0 definiert man die gewöhnliche Generatorfunktion (OGF) als G(x) = sum_{n≥0} a_n x^n. Die Koeffizienten der Reihe entsprechen den Folgewerten, sodass sich Rekursionen oder Zählprobleme in Gleichungen mit G übersetzen lassen. Eine weiter verbreitete Variante ist die exponentielle Generatorfunktion (EGF): A(x) = sum_{n≥0} a_n x^n / n!, die insbesondere dann sinnvoll ist, wenn Objekte nach Größe n gruppiert werden und Reihenfolge ignoriert wird.

Typen und Verwendungen: Die beiden Haupttypen unterscheiden sich durch die Gewichtung der Koeffizienten. OGFs eignen sich gut für natürliche Zählprobleme, während EGFs oft in der Kombinatorik von Mengenstrukturen auftreten. Operationen an Generatorfunktionen spiegeln kombinatorische Operationen wider: Addition entspricht dem Zusammenführen von Strukturen, das Cauchy-Produkt der Konvolution der Folgen, Ableitung verschiebt Indizes und erhöht die Gewichtung entsprechend.

Beispiele: Für a_n = 1 gilt die OGF G(x) = 1/(1−x) (|x|<1). Für a_n = n ergibt sich G(x) = x/(1−x)^2. In der EGF liefert a_n = 1 die Funktion e^x; a_n = n+1 führt zu (e^x)(1+x).

Anwendungen umfassen Zählprobleme in der Kombinatorik, Lösung von Rekursionsbeziehungen, Wahrscheinlichkeitsgenerierende Funktionen und die Analyse von Algorithmen. Die Idee geht auf frühe Arbeiten von Euler und Nachfolgern zurück.