Erzeugende Funktion

In verschiedenen Teilgebieten der Mathematik versteht man unter der erzeugenden Funktion einer Folge ${\displaystyle (a_{n})}$ die formale Potenzreihe

${\displaystyle f(z)=\sum _{n=0}^{\infty }a_{n}z^{n}}$.

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

${\displaystyle f(z)=\sum _{n=0}^{\infty }z^{n}=1z^{0}+1z^{1}+1z^{2}+\ldots }$

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

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

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

Beispiele

Es gelten folgende Identitäten:

• ${\displaystyle \sum _{n=0}^{\infty }nz^{n}={\frac {z}{(1-z)^{2}}}}$     (erzeugende Funktion der Folge der natürlichen Zahlen ${\displaystyle 0,1,2,3,\ldots }$)
• ${\displaystyle \sum _{n=0}^{\infty }n^{2}z^{n}={\frac {z(1+z)}{(1-z)^{3}}}}$     (erzeugende Funktion der Folge der Quadratzahlen ${\displaystyle 0,1,4,9,\ldots }$)
• ${\displaystyle \sum _{n=0}^{\infty }a^{n}z^{n}={\frac {1}{1-az}}}$     (erzeugende Funktion der geometrischen Folge ${\displaystyle 1,a,a^{2},a^{3},\ldots }$)
• ${\displaystyle \sum _{n=0}^{\infty }{c \choose n}z^{n}=(1+z)^{c}}$
• ${\displaystyle \sum _{n=0}^{\infty }{c+n-1 \choose n}z^{n}={\frac {1}{(1-z)^{c}}}}$
• ${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n}}z^{n}=\ln {\frac {1}{1-z}}}$
• ${\displaystyle \sum _{n=0}^{\infty }{\frac {1}{n!}}z^{n}=e^{z}}$

Manipulation von erzeugenden Funktionen

Stellt m​an eine Folge a​ls erzeugende Funktion dar, entsprechen bestimmte Manipulationen d​er Folge entsprechenden Manipulationen d​er erzeugenden Funktion.

Betrachten wir z. B. die Folge ${\displaystyle 1,1,1,\ldots }$ mit der erzeugenden Funktion ${\displaystyle \sum _{n=0}^{\infty }z^{n}={\frac {1}{1-z}}=F(z)}$. Ableiten ergibt

${\displaystyle F'(z)={\frac {1}{(1-z)^{2}}}=\sum _{n=0}^{\infty }(n+1)z^{n}}$.

Das entspricht der Folge ${\displaystyle 1,2,3,\ldots }$ Multiplikation mit ${\displaystyle z}$ ergibt

${\displaystyle zF'(z)={\frac {z}{(1-z)^{2}}}=\sum _{n=0}^{\infty }nz^{n}}$.

Wir erhalten also die Folge ${\displaystyle 0,1,2,3,\ldots }$

Ableiten einer erzeugenden Funktion entspricht also der Multiplikation des n-ten Gliedes der Folge mit ${\displaystyle n}$ und anschließender Indexverschiebung nach links, Multiplikation mit z entspricht einer Verschiebung der Indizes nach rechts.

Betrachten wir eine weitere Folge ${\displaystyle a_{0},a_{1},a_{2},\ldots }$ mit der erzeugenden Funktion ${\displaystyle \sum _{n=0}^{\infty }a_{n}z^{n}=G(z)}$. Multipliziert man ${\displaystyle G(z)}$ mit der erzeugenden Funktion ${\displaystyle F(z)}$ von oben gemäß der Cauchy-Produktformel erhält man:

${\displaystyle G(z)F(z)=G(z){\frac {1}{1-z}}=(\sum _{n=0}^{\infty }a_{n}z^{n})(\sum _{n=0}^{\infty }1z^{n})=\sum _{n=0}^{\infty }(\sum _{k=0}^{n}a_{k}\ 1)z^{n}}$

Der n-te Koeffizient des Produkts ist also von der Form ${\displaystyle \sum _{k=0}^{n}a_{k}}$. Das ist genau die Partialsumme der ersten ${\displaystyle n}$ Koeffizienten der ursprünglichen erzeugenden Funktion. Die Multiplikation einer erzeugenden Funktion mit ${\displaystyle {\frac {1}{1-z}}}$ liefert somit die Partialsummen.

Eine Übersicht über weitere mögliche Manipulationen liefert d​ie folgende Tabelle:

Folge	erzeugende Funktion
${\displaystyle (a_{n}+b_{n})_{n\geq 0}}$	${\displaystyle A(z)+B(z)}$
${\displaystyle (\sum _{k=0}^{n}a_{k}b_{n-k})_{n\geq 0}}$	${\displaystyle A(z)B(z)}$
${\displaystyle (\sum _{k=0}^{n}a_{k})_{n\geq 0}}$	${\displaystyle {\frac {1}{1-z}}A(z)}$
${\displaystyle (\lambda ^{n}a_{n})_{n\geq 0}}$	${\displaystyle A(\lambda z)}$
${\displaystyle ((n+1)a_{n+1})_{n\geq 0}}$	${\displaystyle A'(z)}$
${\displaystyle (na_{n})_{n\geq 0}}$	${\displaystyle zA'(z)}$
${\displaystyle (n^{2}a_{n})_{n\geq 0}}$	${\displaystyle zA'(z)+z^{2}A''(z)}$
${\displaystyle a_{0},0,a_{2},0,a_{4},0,\ldots }$	${\displaystyle {\frac {1}{2}}{\bigl (}A(z)+A(-z){\bigr )}}$
${\displaystyle 0,a_{1},0,a_{3},0,a_{5},\ldots }$	${\displaystyle {\frac {1}{2}}{\bigl (}A(z)-A(-z){\bigr )}}$

${\displaystyle A(z)}$ ist die erzeugende Funktion der Folge ${\displaystyle a_{0},a_{1},a_{2},\ldots =(a_{n})_{n\geq 0}}$, ${\displaystyle B(z)}$ die der Folge ${\displaystyle (b_{n})_{n\geq 0}}$.

Anwendung

Erzeugende Funktionen sind 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 ${\displaystyle z\mapsto z}$ entspricht der Verschiebung der modellierten Folgeglieder um eine Stelle nach hinten, wobei vorn, als neues Glied mit dem Index ${\displaystyle 0}$, eine ${\displaystyle 0}$ angefügt wird. Angenommen, wir haben die Rekursion ${\displaystyle f(n)=2\cdot f(n-1),f(0)=1}$ zu lösen, dann ist ${\displaystyle f(n)\cdot z^{n}=2z\cdot f(n-1)z^{n-1}}$, und es gilt für die erzeugende Funktion

${\displaystyle 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

${\displaystyle F(z)=1+2z\cdot F(z)}$

Auflösen n​ach F liefert

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

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

Verschiedene Typen von erzeugenden Funktionen

Es g​ibt neben d​er gewöhnlichen erzeugenden Funktion n​och weitere Typen v​on erzeugenden Funktionen. Manchmal erweist e​s sich a​ls zweckmäßig, Folgen m​it Hilfe d​er folgenden z​wei Arten v​on erzeugenden Funktionen z​u betrachten.

Exponentiell erzeugende Funktion

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

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

Dirichlet-erzeugende Funktion

Die Dirichlet-erzeugende Funktion einer Folge ${\displaystyle a_{n}}$ ist die Reihe ${\displaystyle 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 ${\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}}$ die Dirichlet-erzeugende Funktion der Folge ${\displaystyle 1,1,1,\ldots }$

Wahrscheinlichkeitserzeugende Funktion

→ Hauptartikel: Wahrscheinlichkeitserzeugende Funktion

Liegen alle ${\displaystyle (a_{i})_{i\in \mathbb {N} }}$ zwischen null und eins und summieren sich zu eins auf, so nennt man die erzeugende Funktion dieser Reihe auch wahrscheinlichkeitserzeugenden Funktion. Sie spielt z. B. eine Rolle bei der Berechnung von Erwartungswerten und Varianzen sowie bei der Addition von unabhängigen Zufallsvariablen.

Erzeugende Funktionen und die Z-Transformation

Sei ${\displaystyle G\{a_{n}\}(z)}$ die gewöhnliche erzeugende Funktion von ${\displaystyle (a_{n})}$ und sei ${\displaystyle {\mathcal {Z}}\{a_{n}\}(z)}$ die unilaterale Z-Transformation von ${\displaystyle (a_{n})}$. Der Zusammenhang zwischen der erzeugenden Funktion und der Z-Transformierten ist

${\displaystyle G\{a_{n}\}(z)={\mathcal {Z}}\{a_{n}\}{\Big (}{\frac {1}{z}}{\Big )}.}$

Aus e​iner Tabelle v​on Z-Transformationen k​ann man d​amit die entsprechenden erzeugenden Funktionen gewinnen u​nd umgekehrt.

Beispiel: Es ist ${\displaystyle {\mathcal {Z}}\{1\}(z)={\frac {z}{z-1}}.}$ Damit ergibt sich

${\displaystyle G\{1\}(z)={\frac {1/z}{1/z-1}}={\frac {z}{z}}\left({\frac {1/z}{1/z-1}}\right)={\frac {1}{1-z}}.}$

Literatur

• Martin Aigner: Diskrete Mathematik. 5., überarbeitete und erweiterte Auflage. Vieweg, Wiesbaden 2004, ISBN 3-528-47268-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).