Erzeugende Funktion

Art von formaler Potenzreihe
(Weitergeleitet von Erzeugende)

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

.

Zum Beispiel ist die erzeugende Funktion der konstanten Folge die geometrische Reihe

Die Reihe konvergiert für alle und besitzt den Wert

.

Wegen der Verwendung formaler Potenzreihen spielen allerdings im Allgemeinen Konvergenzfragen keine Rolle – 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 für die elementaren Funktionen:

  •       (erzeugende Funktion der Folge der natürlichen Zahlen  )
  •       (erzeugende Funktion der Folge der Quadratzahlen  )
  •       (erzeugende Funktion der geometrischen Folge  )
  •  
  •  
  •  
  •  
  •  

Mit dem Kürzel Bₙ wird die Bellsche Zahlenfolge dargestellt.

Die erzeugenden Funktionen mancher Zahlenfolgen sind nicht elementar beschaffen. Durch Srinivasa Ramanujan, Richard Dedekind und Leonhard Euler wurden folgende erzeugende Funktionen für die reguläre Partitionszahlenfolge P(n) und die strikte Partitionszahlenfolge Q(n) ermittelt:

  •  
  •  

Mit dem Buchstaben ϑ werden die elliptischen Theta-Nullwertfunktionen ausgedrückt.

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   mit der erzeugenden Funktion  . Ableiten ergibt

 .

Das entspricht der Folge   Multiplikation mit   ergibt

 .

Wir erhalten also die Folge  

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

Betrachten wir eine weitere Folge   mit der erzeugenden Funktion  . Multipliziert man   mit der erzeugenden Funktion   von oben gemäß der Cauchy-Produktformel erhält man:

 

Der n-te Koeffizient des Produkts ist also von der Form  . Das ist genau die Partialsumme der ersten   Koeffizienten der ursprünglichen erzeugenden Funktion. Die Multiplikation einer erzeugenden Funktion mit   liefert somit die Partialsummen.

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

Folge erzeugende Funktion
   
   
   
   
   
   
   
   
   

  ist die erzeugende Funktion der Folge  ,   die der Folge  .

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   entspricht der Verschiebung der modellierten Folgeglieder um eine Stelle nach hinten, wobei vorn, als neues Glied mit dem Index  , eine   angefügt wird. Angenommen, wir haben die Rekursion   zu lösen, dann ist  , und es gilt für die erzeugende Funktion

 

also

 

Auflösen nach F liefert

 

Wir wissen aber aus dem vorhergehenden Abschnitt, dass dies der Reihe   entspricht, also gilt   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   ist die Reihe  .

Zum Beispiel ist die Exponentialfunktion   die exponentiell erzeugende Funktion der Folge  

Dirichlet-erzeugende Funktion

Bearbeiten

Die Dirichlet-erzeugende Funktion einer Folge   ist die Reihe  . Sie ist benannt nach Peter Gustav Lejeune Dirichlet.

Zum Beispiel ist die Riemannsche Zetafunktion   die Dirichlet-erzeugende Funktion der Folge  

Wahrscheinlichkeitserzeugende Funktion

Bearbeiten

Liegen alle   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   die gewöhnliche erzeugende Funktion von   und sei   die unilaterale Z-Transformation von  . Der Zusammenhang zwischen der erzeugenden Funktion und der Z-Transformierten ist

 

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

Beispiel: Es ist   Damit ergibt sich

 

Literatur

Bearbeiten