Erzeugende Funktion


Erzeugende Funktion

In verschiedenen Teilgebieten der Mathematik versteht man unter der erzeugenden Funktion einer Folge an eine Funktion, deren Werte als formale Potenzreihe

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

darstellbar sind.

Ein einfaches Beispiel ist die erzeugende Funktion der konstanten Folge 1, 1, 1, \ldots

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

Ihr Wert an der Stelle z ist für | z | < 1

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

und folgt aus der Beobachtung

 (1-z) \cdot \sum_{n=0}^{\infty} z^n = 1.

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

Inhaltsverzeichnis

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 der Berechnung von Partitionen. 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}

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) = 2n 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 an ist die Reihe z\mapsto \sum_{n=0}^\infty \frac{a_n}{n!} z^n.

Zum Beispiel ist die Exponentialfunktion ez die exponentiell erzeugende Funktion der Folge 1, 1, 1, \ldots

Dirichlet-erzeugende Funktion

Die Dirichlet-erzeugende Funktion einer Folge an 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

Siehe auch

Literatur


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • erzeugende Funktion — generuojančioji funkcija statusas T sritis fizika atitikmenys: angl. generating function vok. erzeugende Funktion, f rus. производящая функция, f pranc. fonction génératrice, f …   Fizikos terminų žodynas

  • Autokovarianz erzeugende Funktion — Ist eine Zeitreihe schwach stationär (⇡ Stationarität), so ist die ⇡ Kovarianz zwischen der Realisation der Zeitreihe im Zeitpunkt t und der Realisation im Zeitpunkt t–k unabhängig vom Zeitpunkt t und hängt nur von der Länge des ⇡ Lags k ab. Ist… …   Lexikon der Economics

  • Erzeugende — In verschiedenen Teilgebieten der Mathematik versteht man unter der erzeugenden Funktion einer Folge an die formale Potenzreihe Ein einfaches Beispiel ist die erzeugende Funktion der konstanten Folge die Gleichheit gilt nur für | z | < 1 und… …   Deutsch Wikipedia

  • Funktion (Mathematik) — In der Mathematik ist eine Funktion oder Abbildung eine Beziehung zwischen zwei Mengen, die jedem Element der einen Menge (Funktionsargument, unabhängige Variable, x Wert) genau ein Element der anderen Menge (Funktionswert, abhängige Variable, y… …   Deutsch Wikipedia

  • Generierende Funktion — In verschiedenen Teilgebieten der Mathematik versteht man unter der erzeugenden Funktion einer Folge an die formale Potenzreihe Ein einfaches Beispiel ist die erzeugende Funktion der konstanten Folge die Gleichheit gilt nur für | z | < 1 und… …   Deutsch Wikipedia

  • Riemannsche ζ-Funktion — Die riemannsche Zeta Funktion in der komplexen Ebene Die in obigem Bild verwendete Kolo …   Deutsch Wikipedia

  • Rekursive Funktion — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Sprungstetige Funktion — Der Begriff der Sprungstetigen Funktion oder Regelfunktion ist ein wichtiger Begriff in der Integrationstheorie. Inhaltsverzeichnis 1 Definition 2 Einseitige Stetigkeit 2.1 Definition 3 Stieltjes’scher Inhalt 4 …   Deutsch Wikipedia

  • Wahrscheinlichkeitserzeugende Funktion — In der Wahrscheinlichkeitstheorie ist die wahrscheinlichkeitserzeugende Funktion einer wertigen Zufallsvariable X definiert durch für . Eigenschaften Die wahrscheinlichkeitserzeugende Funktion bestimmt die Verteilung von X eindeutig: Ist …   Deutsch Wikipedia

  • Algebraische Funktion — In der Mathematik ist eine Funktion oder Abbildung eine Beziehung zwischen zwei Mengen, die jedem Element der einen Menge (Eingangsgröße, Funktionsargument, unabhängige Variable, x Wert) ein Element der anderen Menge (Ausgangsgröße, Funktionswert …   Deutsch Wikipedia