Erzeugende Funktion

In verschiedenen Teilgebieten der Mathematik versteht man unter der erzeugenden Funktion einer Folge $a_n$ die formale Potenzreihe

$f(z) = \sum_{n=0}^{\infty} a_n z^n.$

Zum Beispiel ist die erzeugende Funktion der konstanten Folge $1, 1, 1, \ldots$ die geometrische Reihe

$f(z) = \sum_{n=0}^{\infty} z^n.$

Die Reihe konvergiert für alle $|z|<1$ und besitzt den Wert

$f(z) = \frac{1}{1-z}$

Wegen der Verwendung formaler Potenzreihen spielen allerdings im Allgemeinen Konvergenzfragen keine Rolle – $z$ ist lediglich ein Symbol. Diese explizitere Darstellung als Potenzreihe ermöglicht oft Rückschlüsse auf die Folge.

Explizite Formeln für einige wichtige Potenzreihen

Es gelten folgende Identitäten:

• $\sum_{n=0}^{\infty} z^n = \frac{1}{1-z}$
• $\sum_{n=0}^{\infty} n z^n = \frac{z}{(1-z)^2}$
• $\sum_{n=0}^{\infty} n^2 z^n = \frac{z(1+z)}{(1-z)^3}$
• $\sum_{n=0}^{\infty} a^n z^n = \frac{1}{1 - az}$
• $\sum_{n=0}^{\infty} {c \choose n} z^n = (1 + z)^c$
• $\sum_{n=0}^{\infty} {c + n - 1 \choose n} a^n z^n = \frac{1}{(1-az)^c}$
• $\sum_{n=1}^{\infty} \frac{1}{n}z^n = \ln \frac{1}{1-z}$
• $\sum_{n=0}^{\infty} \frac{1}{n!}z^n = e^z$

Anwendung

Erzeugende Funktionen liefern ein wichtiges Hilfsmittel für das Lösen von Rekursionen und Differenzengleichungen sowie für das Zählen von Zahlpartitionen. Die punktweise Multiplikation einer erzeugenden Funktion mit der Identität $z\mapsto z$ entspricht der Verschiebung der modellierten Folgeglieder um eine Stelle nach hinten, wobei vorn, als neues Glied mit dem Index $0$, eine $0$ angefügt wird. Angenommen, wir haben die Rekursion $f(n) = 2\cdot f(n-1), f(0) = 1$ zu lösen, dann ist $f(n)\cdot z^n = 2z\cdot f(n-1) z^{n-1}$, und es gilt für die erzeugende Funktion

$F(z) := \sum_{n=0}^\infty f(n) \cdot z^{n} = f(0) + \sum_{n=1}^\infty f(n) \cdot z^{n}= 1 + 2z\cdot \sum_{n=1}^\infty f(n-1) \cdot z^{n-1} = 1 + 2z\cdot \sum_{n=0}^\infty f(n) \cdot z^n$

also

$F(z) = 1+ 2z \cdot F(z)$

Auflösen nach F liefert

$F(z) = \frac{1}{1 - 2z}.$

Wir wissen aber aus dem vorhergehenden Abschnitt, dass dies der Reihe $\sum_{n=0}^\infty 2^n z^n$ entspricht, also gilt $f(n) = 2^n$ nach Koeffizientenvergleich.

Verschiedene Typen von erzeugenden Funktionen

Es gibt neben der gewöhnlichen erzeugenden Funktion noch weitere Typen von erzeugenden Funktionen. Manchmal erweist es sich als zweckmäßig, Folgen mit Hilfe der folgenden zwei Arten von erzeugenden Funktionen zu betrachten.

Exponentiell erzeugende Funktion

Die exponentiell erzeugende Funktion (oder erzeugende Funktion vom Exponentialtyp) einer Folge $a_n$ ist die Reihe $z\mapsto \sum_{n=0}^\infty \frac{a_n}{n!} z^n$.

Zum Beispiel ist die Exponentialfunktion $e^z$ die exponentiell erzeugende Funktion der Folge $1, 1, 1, \ldots$

Dirichlet-erzeugende Funktion

Die Dirichlet-erzeugende Funktion einer Folge $a_n$ ist die Reihe $s\mapsto \sum_{n=1}^{\infty} \frac{a_n}{n^s}$. Sie ist benannt nach Peter Gustav Lejeune Dirichlet.

Zum Beispiel ist die Riemannsche Zetafunktion $\zeta(s) = \sum_{n=1}^\infty\frac{1}{n^s}$ die Dirichlet-erzeugende Funktion der Folge $1, 1, 1, \ldots$

Die „Zustandsumme“ als erzeugende Funktion in der Thermodynamik

In der Statistischen Physik, einer theoretisch-physikalischen Disziplin, in der vor allem die Thermodynamik behandelt wird, bezeichnet man als Zustandssumme (Partition function) die formale Potenzreihe $\mathcal Z(\beta )\,:=\sum \exp{(-\beta E_n)} ,$ worin β im Wesentlichen die reziproke Temperatur 1/T und E_n die als diskret angenommenen Energiewerte des behandelten Systems sind. Die „Zustandssumme“ ist die „Erzeugende Funktion“ einer großen Zahl sogenannter thermodynamischer Potentiale, insbesondere der Inneren Energie $U(T)=-\mathrm d\,\ln \mathcal{Z}/\mathrm d\beta ,$ der Freien Energie $F(T):= -T\cdot \ln \mathcal Z$ und der Entropie $S(T) :=(U(T)-F(T))/T =\ln\mathcal{Z}-\beta\cdot\mathrm d\,\ln\mathcal{Z}/\mathrm d\beta .$.

  Durch Ableitung nach einem Parameter β erzeugte Beziehungen, analog zur Beziehung zwischen $U(T)$ und $\ln\mathcal Z,$ treten im Zusammenhang mit dem Begriff des Pfadintegrals auch in anderen Gebieten der Theoretischen Physik auf. Für diese Beziehungen wird ebenfalls der Begriff der „erzeugenden Funktion“ verwendet, auch wenn man es nicht mit Potenzreihen zu tun hat.

Siehe auch

• Wahrscheinlichkeitserzeugende Funktion

Literatur

 Wikibooks: Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen – Lern- und Lehrmaterialien

• Martin Aigner: Diskrete Mathematik. 5., überarbeitete und erweiterte Auflage. Vieweg, Wiesbaden 2004, ISBN 3-528-47-268-5.
• Herbert S. Wilf: generatingfunctionology. 3. Auflage. A. K. Peters Ltd., Wellesley MA 2005, ISBN 978-1-56881-279-3 (2. Auflage. Academic Press, Boston MA u. a. 1994, ISBN 0-12-751956-4, im PDF 1,18 MB).