Rekursionen und erzeugende Funktionen: Zählen, Lösen, Wachstum

Wie viele Möglichkeiten gibt es, einen Turm aus $n$ Scheiben umzusetzen, wie viele Zahlenfolgen aus $0$ und $1$ ohne zwei Einsen nebeneinander gibt es, wie viele Wege führen durch ein Gitter? Bei solchen Fragen ist die Antwort für $n$ oft leicht durch die Antworten für kleinere Werte auszudrücken. Das ist eine Rekursion. Daraus eine geschlossene Formel zu gewinnen, ist Handwerk der diskreten Mathematik, und es gibt zwei große Werkzeuge: die charakteristische Gleichung und die erzeugenden Funktionen.

Die Seite setzt die Kombinatorik und die vollständige Induktion voraus. Eine bekannte Rekursion, die Fibonacci-Folge, hat eine eigene Seite: Fibonacci-Folge.

Rekursionen

Eine Rekursion definiert die Glieder einer Folge durch frühere Glieder und Anfangswerte. Die Fakultät folgt $n!=n·(n-1)!$ mit $0!=1$. Bei den Türmen von Hanoi sollen $n$ Scheiben von einem Stab auf einen anderen umgesetzt werden, wobei nie eine größere auf einer kleineren liegen darf. Um die größte Scheibe zu bewegen, muss der Turm der $n-1$ kleineren erst auf den Hilfsstab ($h_{n-1}$ Züge), dann kommt die große Scheibe (1 Zug), und danach wird der kleine Turm wieder darauf gesetzt ($h_{n-1}$ Züge). Also gilt $h_n=2h_{n-1}+1$ mit $h_0=0$. Die ersten Werte $0,1,3,7,15,\dots$ legen die Vermutung $h_n=2^n-1$ nahe, und der Induktionsschritt bestätigt sie: $h_n=2(2^{n-1}-1)+1=2^n-1$. Für $64$ Scheiben sind das etwa $\mathrm{1,8}·{10}^{19}$ Züge.

Lineare Rekursionen mit konstanten Koeffizienten

Die Rekursion $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}$ mit festen Zahlen $c_1,c_2$ und Anfangswerten $a_0,a_1$ lässt sich geschlossen lösen. Der Ansatz $a_n={\lambda }^n$ führt nach Kürzen von ${\lambda }^{n-2}$ auf die charakteristische Gleichung ${\lambda }^2=c_1\lambda +c_2$.

Beweis. Einsetzen zeigt, dass ${\lambda }_1^n$ und ${\lambda }_2^n$ die Rekursion erfüllen. Wegen der Linearität gilt das auch für jede Kombination. Die Anfangswerte liefern $\alpha +\beta =a_0$ und $\alpha {\lambda }_1+\beta {\lambda }_2=a_1$, ein Gleichungssystem mit der Determinante ${\lambda }_2-{\lambda }_1\ne 0$, also eindeutig lösbar. Weil eine Folge durch Rekursion und Anfangswerte schon eindeutig bestimmt ist, gibt es keine weiteren Lösungen. Bei einer doppelten Nullstelle prüft man $n{\lambda }^n$ direkt: Aus ${\lambda }^2-c_1\lambda -c_2={(\lambda -{\lambda }_0)}^2$ folgt $c_1=2{\lambda }_0$ und $c_2=-{\lambda }_0^2$, und $c_1(n-1){\lambda }_0^{n-1}+c_2(n-2){\lambda }_0^{n-2}={\lambda }_0^n(2(n-1)-(n-2))=n{\lambda }_0^n$. $\square$

Für die Fibonacci-Folge $f_n=f_{n-1}+f_{n-2}$ ist ${\lambda }^2=\lambda +1$ mit den Lösungen $\lambda =\frac{1\pm \sqrt{5}}{2}$, und die Anfangswerte $f_0=0$, $f_1=1$ liefern die Formel von Moivre und Binet $f_n=\frac{{\Phi }^n-{\Psi }^n}{\sqrt{5}}$ mit $\Phi =\frac{1+\sqrt{5}}{2}$ und $\Psi =\frac{1-\sqrt{5}}{2}$.

Erzeugende Funktionen

Man rechnet meist formal und fragt nicht nach Konvergenz: $x$ ist nur ein Symbol. Wichtige Bausteine sind die geometrische Reihe $\frac{1}{1-x}=\sum x^n$ (die Folge $1,1,1,\dots$), $\frac{1}{1-ax}=\sum a^n{x}^n$, $\frac{x}{{(1-x)}^2}=\sum n{x}^n$ und der binomische Lehrsatz ${(1+x)}^n=\sum \left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k$. Die Rechenregeln: Die Multiplikation mit $x$ verschiebt die Folge, die Summe zweier Funktionen gehört zur Summe der Folgen, und das Produkt zweier Funktionen gehört zur Faltung: $(\sum a_n{x}^n)(\sum b_n{x}^n)=\sum c_n{x}^n$ mit $c_n=\sum _{k=0}^n{a}_k{b}_{n-k}$.

Rekursionen lösen

Das Verfahren hat drei Schritte: Rekursion mit $x^n$ multiplizieren und über $n$ summieren, eine Gleichung für $G$ aufstellen und lösen, dann $G$ in eine Potenzreihe entwickeln (meist mit Partialbruchzerlegung). Für $h_n=2h_{n-1}+1$ mit $h_0=0$ ergibt die Summe $G(x)=2xG(x)+\frac{x}{1-x}$, also $G(x)=\frac{x}{(1-x)(1-2x)}=\frac{1}{1-2x}-\frac{1}{1-x}$ und damit $h_n=2^n-1$. Bei Fibonacci erhält man $G(x)(1-x-x^2)=x$, also $G(x)=\frac{x}{1-x-x^2}$, und die Partialbruchzerlegung liefert die Formel von Binet.

Zählen mit erzeugenden Funktionen

Der eigentliche Vorteil zeigt sich beim Zählen. Eine Münze, die beliebig oft benutzt werden darf, entspricht einem Faktor $\frac{1}{1-x^w}$ (Wert $w$). Die Anzahl der Möglichkeiten, $n$ Euro mit Ein- und Zwei-Euro-Münzen zu bezahlen (die Reihenfolge ist egal), ist der Koeffizient von $x^n$ in $\frac{1}{(1-x)(1-x^2)}$. Er ist $\lfloor \frac{n}{2}\rfloor +1$, denn zu jeder Zahl $k$ von Zwei-Euro-Münzen mit $2k\le n$ gehört genau eine Aufteilung. Für $n=4$ sind es die drei Möglichkeiten $1+1+1+1$, $2+1+1$ und $2+2$.

Ein weiteres Beispiel sind die Catalan-Zahlen $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$, die $1,1,2,5,14,42,\dots$ zählen. Sie geben die Zahl der korrekt geklammerten Ausdrücke mit $n$ Klammerpaaren oder die Zahl der Möglichkeiten, ein $(n+2)$-Eck in Dreiecke zu zerlegen. Sie erfüllen $C_{n+1}=\sum _{k=0}^n{C}_k{C}_{n-k}$. Für die erzeugende Funktion $C(x)$ ist das $C(x)=1+xC{(x)}^2$ mit der Lösung $C(x)=\frac{1-\sqrt{1-4x}}{2x}$.

Inklusion und Exklusion

Für zwei Mengen gilt $|A\cup B|=\left|A\right|+\left|B\right|-|A\cap B|$: Die Elemente im Durchschnitt werden beim Addieren zweimal gezählt und müssen einmal wieder abgezogen werden. Für drei Mengen ist $|A\cup B\cup C|=\left|A\right|+\left|B\right|+\left|C\right|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$.

Beweis. Ein Element, das in genau $m\ge 1$ der Mengen liegt, wird auf der rechten Seite in jedem Durchschnitt $\bigcap _{i\in I}{A}_i$ mit $I\subseteq$ (diesen $m$ Indizes) gezählt, und zwar $\left(\genfrac{}{}{0ex}{}{m}{j}\right)$-mal für $\left|I\right|=j$ mit dem Vorzeichen ${(-1)}^{j+1}$. Insgesamt ist sein Beitrag $\sum _{j=1}^m{(-1)}^{j+1}\left(\genfrac{}{}{0ex}{}{m}{j}\right)=1-\sum _{j=0}^m{(-1)}^j\left(\genfrac{}{}{0ex}{}{m}{j}\right)=1-{(1-1)}^m=1$. Es wird also genau einmal gezählt. $\square$

Auch die Zahl der surjektiven Abbildungen von einer $n$-elementigen Menge auf eine $m$-elementige lässt sich so zählen: $\sum _{k=0}^m{(-1)}^k\left(\genfrac{}{}{0ex}{}{m}{k}\right){(m-k)}^n$. Für $n=4$ und $m=3$ sind es $81-3·16+3·1=36$.

Wachstum von Funktionen: die O-Notation

Zur Beurteilung eines Verfahrens zählt, wie stark seine Rechenzeit mit der Eingabegröße $n$ wächst. Dafür vergleicht man Funktionen bis auf konstante Faktoren und endlich viele Ausnahmen.

Zum Beispiel ist $3n^2+5n=\Theta (n^2)$, denn $n^2\le 3n^2+5n\le 8n^2$ für $n\ge 1$. Die Rangfolge der wichtigsten Funktionen ist $1\prec \log n\prec \sqrt{n}\prec n\prec n\log n\prec n^2\prec n^3\prec 2^n\prec n!$. Ein Polynom wächst langsamer als jede Exponentialfunktion $a^n$ mit $a>1$, und die Fakultät schneller als jede Exponentialfunktion.

Rekursionen der Form $T(n)=aT(n/b)+n^d$ (Teile und herrsche) haben nach dem Mastertheorem die Lösung

Für die Sortierung durch Mischen ist $T(n)=2T(n/2)+n$, also $a=b=2$, $d=1={\log }_{}2$, und die Laufzeit ist $\Theta (n\log n)$. Die binäre Suche hat $T(n)=T(n/2)+1$ ($a=1$, $b=2$, $d=0={\log }_{}1$) und damit $\Theta (\log n)$. Die Multiplikation nach Karatsuba kommt mit $T(n)=3T(n/2)+n$ auf $\Theta (n^{{\log }_{}3})\approx \Theta (n^{\mathrm{1,585}})$, besser als die schriftliche Multiplikation mit $\Theta (n^2)$. Dagegen braucht die naive rekursive Berechnung der Fibonacci-Zahlen $\Theta ({\Phi }^n)$ Schritte, während eine Schleife mit $n$ Additionen genügt.

Übungen

Immer neue Aufgaben mit Lösungen gibt es auf dem Blatt Rekursionen, Siebformel und Mastertheorem.

Geschichte: von den Kaninchen zu den Siebformeln

Die berühmteste Rekursion stammt aus dem „Liber Abaci“, in dem Leonardo von Pisa 1202 das Wachstum einer Kaninchenpopulation beschrieb. Die geschlossene Formel entdeckte Abraham de Moivre 1718, Daniel Bernoulli lieferte vermutlich 1728 den ersten Beweis, und Jacques Binet fand sie 1843 noch einmal unabhängig. Mit erzeugenden Funktionen löste de Moivre ab 1730 Rekursionen. Pierre-Simon Laplace baute 1814 in seiner „Théorie analytique des probabilités“ eine ausführliche Theorie dazu auf, aus der die Laplace-Transformation hervorging. Die Siebformel wurde von de Moivre, Daniel da Silva, James Joseph Sylvester und Henri Poincaré weiterentwickelt und heißt deshalb auch Formel von Poincaré und Sylvester.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Erzeugende Funktion
• Wikipedia: Fibonacci-Folge
• Wikipedia: Inklusions-Exklusions-Prinzip
• Martin Aigner: Diskrete Mathematik, Springer Spektrum, Wiesbaden.
• Herbert S. Wilf: generatingfunctionology, A K Peters, Wellesley.
• Ronald Graham, Donald Knuth, Oren Patashnik: Concrete Mathematics, Addison-Wesley.