~2025-30310-79: /* Manipulation von erzeugenden Funktionen */

2025-10-29T16:38:22Z

Manipulation von erzeugenden Funktionen

Neue Seite

In der Mathematik versteht man unter der (gewöhnlichen) '''erzeugenden Funktion''' einer [[Folge (Mathematik)|Folge]] <math> (a_n) </math> die [[formale Potenzreihe]]
: <math> A(z) = \sum_{n=0}^{\infty} a_n z^n </math>.

Sie findet Verwendung in der [[Kombinatorik]], [[Analysis]], [[Algebra]], [[Zahlentheorie]], [[Wahrscheinlichkeitstheorie]] und in der [[Diskrete Mathematik|Diskreten Mathematik]].

Zum Beispiel ist die erzeugende Funktion der unendlichen konstanten Folge <math>(1,\, 1,\, 1,\, \ldots)</math> die [[geometrische Reihe]]
: <math> A(z) = \sum_{n=0}^{\infty} z^n = 1 \cdot z^0 + 1 \cdot z^1 + 1 \cdot z^2 + \ldots\,.</math>

Die Reihe konvergiert für alle <math> |z| < 1 </math> und gegen den Wert
: <math> A(z) = \frac{1}{1-z}\,.</math>

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

== Beispiele ==
Es gelten folgende Identitäten für die [[Elementare Funktion|elementaren Funktionen]]:

{| class="wikitable"
! <math> a_n </math>
! colspan="2"| <math> A_n </math>
! erzeugende Funktion der
|-
| <math> n </math>
|style="border-right:0"| <math> \sum_{n=0}^{\infty} n z^n </math> ||style="border-left:0"| <math> = \frac{z}{(1-z)^2}\quad </math> || Folge der [[Natürliche Zahl|natürlichen Zahlen]]<br> <math>( 0, 1, 2, 3, \ldots )</math>
|-
| <math> n^2 </math>
|style="border-right:0"| <math> \sum_{n=0}^{\infty} n^2 z^n </math> ||style="border-left:0"| <math> = \frac{z(1+z)}{(1-z)^3} </math> || Folge der Quadratzahlen<br> <math>( 0, 1, 4, 9, \ldots )</math>
|-
| <math> a^n </math>
|style="border-right:0"| <math> \sum_{n=0}^{\infty} a^n z^n </math> ||style="border-left:0"| <math> = \frac{1}{1 - az} </math> || [[Geometrische Folge|geometrischen Folge]]<br> <math>( 1, a, a^2, a^3, \ldots )</math>
|-
| <math> {c \choose n} </math>
|style="border-right:0"| <math> \sum_{n=0}^{\infty} {c \choose n} z^n </math> ||style="border-left:0"| <math> = (1 + z)^c </math> ||
|-
| <math>\! {c + n - 1 \choose n}\!\! </math>
|style="border-right:0"| <math> \sum_{n=0}^{\infty} {c + n - 1 \choose n} z^n </math> ||style="border-left:0"| <math> = \frac{1}{(1-z)^c} </math> ||
|-
| <math> \frac{1}{n} </math>
|style="border-right:0"| <math> \sum_{n=1}^{\infty} \frac{1}{n}z^n </math> ||style="border-left:0"| <math> = \ln \frac{1}{1-z} </math> ||
|-
| <math> \frac{1}{n!} </math>
|style="border-right:0"| <math> \sum_{n=0}^{\infty} \frac{1}{n!}z^n </math> ||style="border-left:0"| <math> = \mathrm e^z </math> ||
|-
| <math> \frac{B_n}{n!} </math>
|style="border-right:0"| <math> \sum_{n=0}^{\infty} \frac{B_n}{n!}z^{n} </math> ||style="border-left:0"| <math> = \mathrm e^{\mathrm e^z-1}</math> ||
|}

Mit dem Kürzel <math>B_n</math> wird die [[Bellsche Zahl|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 [[Partitionsfunktion|reguläre Partitionszahlenfolge]] <math>P(n)</math> und die strikte Partitionszahlenfolge <math>Q(n)</math> ermittelt:

:{|
| <math> \sum_{n=0}^{\infty} P(n)z^n </math> || <math> = (z;z\;)_{\infty}^{-1} </math> || <math> = \vartheta_{00}(z)^{-1/6}\vartheta_{01}(z)^{-2/3}\biggl\{\frac{1}{16z}\bigl[\vartheta_{00}(z)^4 - \vartheta_{01}(z)^4\bigr]\biggr\}^{-1/24}</math>
|-
| <math> \sum_{n=0}^{\infty} Q(n)z^n </math> || <math> = (z;z^2)_{\infty}^{-1} </math> || <math> = \vartheta_{00}(z)^{+1/6}\vartheta_{01}(z)^{-1/3}\biggl\{\frac{1}{16z}\bigl[\vartheta_{00}(z)^4 - \vartheta_{01}(z)^4\bigr]\biggr\}^{+1/24}</math>
|}

Mit dem Buchstaben <math>\vartheta</math> werden die [[Jacobische Thetafunktion|elliptischen Theta-Nullwertfunktionen]] ausgedrückt.

== Manipulation von erzeugenden Funktionen ==

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

Betrachten wir z. B. die Folge <math>(1,\, 1,\, 1,\, \ldots)</math> mit der erzeugenden Funktion
: <math> B(z) = \sum_{n=0}^{\infty} z^n = \frac{1}{1-z}\,.</math>

Ableiten ergibt
: <math> B'(z) = \frac{1}{(1-z)^2} = \sum_{n=0}^{\infty} (n+1) z^n\,.</math>

Das entspricht der Folge <math>(1,\, 2,\, 3,\, \ldots)</math>
[[Multiplikation]] mit <math>z</math> ergibt
: <math>z\ \! B'(z) = \frac{z}{(1-z)^2} = \sum_{n=0}^{\infty} n z^n\,.</math>

Wir erhalten also die Folge <math>(0,\, 1,\, 2,\, 3,\, \ldots)\,.</math>

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

Betrachten wir eine weitere Folge <math>(a_0,\, a_1,\, a_2,\, \ldots)</math> mit der erzeugenden Funktion <math>\sum_{n=0}^{\infty} a_n z^n = A(z)</math>. <br>
Multipliziert man <math>A(z)</math> mit der erzeugenden Funktion <math>B(z)</math> von oben gemäß der [[Cauchy-Produktformel]] erhält man

: <math>A(z) B(z) = A(z) \frac{1}{1-z} = \bigg(\sum_{n=0}^{\infty} a_n z^n\bigg) \bigg(\sum_{n=0}^{\infty} 1 \cdot z^n\bigg) = \sum_{n=0}^{\infty} \bigg(\sum_{k=0}^{n} a_k \cdot 1\bigg) z^n\,.</math>

Der n-te Koeffizient des Produkts ist also von der Form <math>\sum_{k=0}^{n} a_k</math>. Das ist genau die [[Partialsumme]] der ersten <math>n</math> Koeffizienten der ursprünglichen erzeugenden Funktion. Die Multiplikation einer erzeugenden Funktion mit <math>\frac{1}{1-z}</math> liefert somit die Partialsummen.

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

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

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

== Anwendung ==
Erzeugende Funktionen sind ein wichtiges Hilfsmittel für das Lösen von [[Rekursion]]en und [[Differenzengleichung]]en sowie für das Zählen von [[Partitionsfunktion|Zahlpartitionen]]. Die punktweise Multiplikation einer erzeugenden Funktion mit der Identität <math>z\mapsto z</math> entspricht der Verschiebung der modellierten Folgeglieder um eine Stelle nach hinten, wobei vorn, als neues Glied mit dem Index <math>0</math>, eine <math>0</math> angefügt wird. Angenommen, wir haben die
Rekursion <math>f_n = 2f_{n-1},\ f_0 = 1</math> zu lösen, dann ist <math> f_n \cdot z^n = 2 z\cdot f_{n-1} z^{n-1}</math>, und es gilt für die erzeugende Funktion
: <math> F(z) := \sum_{n=0}^\infty f_n \cdot z^{n} = f_0 + \sum_{n=1}^\infty f_n \cdot z^{n}= 1 + 2z \sum_{n=1}^\infty f_{n-1} \cdot z^{n-1} = 1 + 2z \sum_{n=0}^\infty f_n \cdot z^n</math>

also
: <math> F(z) = 1+ 2z \cdot F(z) </math>

Auflösen nach F liefert
: <math> F(z) = \frac{1}{1 - 2z}\,.</math>

Wir wissen aber aus dem vorhergehenden Abschnitt, dass dies der Reihe <math> \sum_{n=0}^\infty 2^n z^n </math> entspricht, also gilt <math> f_n = 2^n </math> 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 (nicht-gewöhnlichen) erzeugenden Funktionen zu betrachten.

=== Exponentiell erzeugende Funktion ===
Die ''exponentiell erzeugende Funktion'' (oder ''erzeugende Funktion vom Exponentialtyp'') einer Folge <math>a_n</math> ist die Reihe
: <math>z\mapsto \sum_{n=0}^\infty \frac{a_n}{n!} z^n\,.</math>

Die [[Exponentialfunktion]] <math>e^z</math> ist z. B. die exponentiell erzeugende Funktion der Folge <math>(1,\, 1,\, 1,\, \ldots)\,</math>.

=== Dirichlet-erzeugende Funktion ===
Die ''Dirichlet-erzeugende Funktion'' einer Folge <math>a_n</math> ist die Reihe
: <math>s\mapsto \sum_{n=1}^{\infty} \frac{a_n}{n^s}\,.</math>
Sie ist benannt nach [[Peter Gustav Lejeune Dirichlet]].

Die [[Riemannsche Zetafunktion]] <math>\zeta(s) = \sum_{n=1}^\infty\frac{1}{n^s}</math> ist z. B. die Dirichlet-erzeugende Funktion der Folge <math>(1,\, 1,\, 1,\, \ldots)\,</math>.

=== Wahrscheinlichkeitserzeugende Funktion ===
{{Hauptartikel|Wahrscheinlichkeitserzeugende Funktion}}
Liegen alle <math> (a_i)_{i\in \mathbb{N}} </math> zwischen 0 und 1 und summieren sich zu 1 auf, so nennt man die erzeugende Funktion dieser Reihe auch ''wahrscheinlichkeitserzeugenden Funktion''. Sie spielt z. B. eine Rolle bei der Berechnung von [[Erwartungswert]]en und [[Varianz (Stochastik)|Varianzen]] sowie bei der Addition von unabhängigen [[Zufallsvariable]]n.

== Erzeugende Funktionen und die Z-Transformation ==

Sei <math>G\{a_n\}(z)</math> die gewöhnliche erzeugende Funktion von <math>(a_n)</math> und sei <math>\mathcal Z\{a_n\}(z)</math> die unilaterale [[Z-Transformation]] von <math>(a_n)</math>. Der Zusammenhang zwischen der erzeugenden Funktion und der Z-Transformierten ist
:<math>G\{a_n\}(z) = \mathcal Z\{a_n\}\Big(\frac{1}{z}\Big).</math>
Aus einer Tabelle von Z-Transformationen kann man damit die entsprechenden erzeugenden Funktionen gewinnen und umgekehrt.

Beispiel: Es ist
<math>\mathcal Z\{1\}(z) = \frac{z}{z-1}.</math>
Damit ergibt sich
:<math>G\{1\}(z) = \frac{1/z}{1/z-1} = \frac{z}{z}\left(\frac{1/z}{1/z-1}\right)
= \frac{1}{1-z}.</math>

== Literatur ==
{{Wikibooks|Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen}}
* [[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, [https://www2.math.upenn.edu/~wilf/DownldGF.html im PDF 1,18 MB]).

[[Kategorie:Diskrete Mathematik]]

Erzeugende Funktion - Versionsgeschichte

~2025-30310-79: /* Manipulation von erzeugenden Funktionen */