Erzeugende Funktion

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 = 1 z^0 + 1 z^1 + 1 z^2 + \ldots

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.

Beispiele[Bearbeiten]

Es gelten folgende Identitäten:

  •  \sum_{n=0}^{\infty} n z^n = \frac{z}{(1-z)^2}     (erzeugende Funktion der Folge  0, 1, 2, 3, \ldots )
  •  \sum_{n=0}^{\infty} n^2 z^n = \frac{z(1+z)}{(1-z)^3}     (erzeugende Funktion der Folge  0, 1, 4, 9, \ldots )
  •  \sum_{n=0}^{\infty} a^n z^n = \frac{1}{1 - az}     (erzeugende Funktion der Folge  1, a^1, a^2, a^3, \ldots )
  •  \sum_{n=0}^{\infty} {c \choose n} z^n = (1 + z)^c
  •  \sum_{n=0}^{\infty} {c + n - 1 \choose n} z^n = \frac{1}{(1-z)^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

Manipulation von erzeugenden Funktionen[Bearbeiten]

Stellt man eine Folge als erzeugende Funktion dar, entsprechen bestimmte Manipulationen der Folge entsprechenden Manipulationen der erzeugenden Funktion.

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

F'(z) = \frac{1}{(1-z)^2} = \sum_{n=0}^{\infty} (n+1) z^n .

Das entspricht der Folge 1, 2, 3, \ldots Multiplikation mit z ergibt

z F'(z) = \frac{z}{(1-z)^2} = \sum_{n=0}^{\infty} n z^n .

Wir erhalten also die Folge 0, 1, 2, 3, \ldots

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

Betrachten wir eine weitere Folge a_0, a_1, a_2, \ldots mit der erzeugenden Funktion \sum_{n=0}^{\infty} a_n z^n = G(z). Multipliziert man G(z) mit der erzeugenden Funktion F(z) von oben gemäß der Cauchy-Produktformel erhält man:

G(z) F(z) = G(z) \frac{1}{1-z} = (\sum_{n=0}^{\infty} a_n z^n) (\sum_{n=0}^{\infty} 1 z^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 \sum_{k=0}^{n} a_k. Das ist genau die Partialsumme der ersten n Koeffizienten der ursprünglichen erzeugenden Funktion. Die Multiplikation einer erzeugenden Funktion mit \frac{1}{1-z} liefert somit die Partialsummen.

Eine Übersicht über weitere mögliche Manipulationen liefert die folgende Tabelle:

Folge erzeugende Funktion
(a_n + b_n)_{n \geq 0} A(z) + B(z)
(\sum_{k=0}^n a_k b_{n-k})_{n \geq 0} A(z)B(z)
(\sum_{k=0}^n a_k)_{n \geq 0} \frac{1}{1-z}A(z)
(\lambda^n a_n)_{n \geq 0} A(\lambda z)
((n+1) a_{n+1})_{n \geq 0} A'(z)
(n a_n)_{n \geq 0} z A'(z)
(n^2 a_n)_{n \geq 0} z A'(z) + z^2 A''(z)
a_0, 0, a_2, 0, a_4, 0, \ldots \frac{1}{2}\bigl(A(z) + A(-z)\bigr)
0, a_1, 0, a_3, 0, a_5, \ldots \frac{1}{2}\bigl(A(z) - A(-z)\bigr)

A(z) ist die erzeugende Funktion der Folge a_0, a_1, a_2, \ldots = (a_n)_{n \geq 0}, B(z) die der Folge (b_n)_{n \geq 0}.

Anwendung[Bearbeiten]

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 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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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 „Zustandssumme“ als erzeugende Funktion in der Thermodynamik[Bearbeiten]

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 En 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.

Wahrscheinlichkeitserzeugende Funktion[Bearbeiten]

Liegen alle  (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[Bearbeiten]

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

G\{a_n\}(z) = \mathcal Z\{a_n\}\Big(\frac{1}{z}\Big).

Aus einer Tabelle von Z-Transformationen kann man damit die entsprechenden erzeugenden Funktionen gewinnen und umgekehrt.

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

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[Bearbeiten]