Diskrete Mathematik

Marcel Erne

Fakultat fur Mathematik und Physik

Vorlesungfur Studierende des

Bachelor- und Master-Studienganges Mathematik

Sommersemester 2011

4. Analytische Methoden der Kombinatorik

98

Inhaltsverzeichnis

4 Analytische Methoden der Kombinatorik 1004.1 Formale Potenzreihen und erzeugende Funktionen . . . . . . . . 1004.2 Exponentiell erzeugende Funktionen . . . . . . . . . . . . . . . . 1124.3 Rekursionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1194.4 Großenordnung und Asymptotik . . . . . . . . . . . . . . . . . . 137

99

4 Analytische Methoden der Kombinatorik

4.1 Formale Potenzreihen und erzeugende Funktionen

Potenzreihen sind ein bekanntes und wirkungsvolles Werkzeug der Analysis. Inder Kombinatorik ermoglichen sie sowohl besonders kompakte und elegante Dar-stellungen von Anzahlformeln als auch nutzliche Methoden zu deren Auffindung.Der wesentliche neue Aspekt gegenuber der klassischen Analysis ist allerdings,dass grundsatzlich keinerlei Konvergenzvoraussetzungen gemacht werden. Dasist insofern wichtig, als viele Anzahlen so groß sind, dass die entsprechenden Po-tenzreihen mit diesen Koeffizienten nur im Nullpunkt konvergieren wurden unddaher nicht aus der dargestellten Funktion zuruckgewonnen werden konnen. Insolchen Fallen ist die ubliche Bezeichnung ”erzeugende Funktionen” etwas irre-fuhrend.

Beispiel 4.1 Eine erzeugende FunktionDie Anzahl der Teilmengen einer n-elementigen Menge ist 2n. Die zugehorigeerzeugende Funktion ist

∞∑n=0

2nxn =1

1− 2xmit Konvergenzradius

12.

Hingegen ist die ”erzeugende Funktion” der Anzahlen 2n2

aller Relationen aufn die unendliche Reihe

∞∑n=0

2n2xn mit Konvergenzradius 0.

Es gibt also keine analytische Funktion mit den Taylorkoeffizienten 2n2.

Wir gehen deshalb den Weg der Algebra und definieren formale Potenzreiheneinfach durch die Folge ihrer Koeffizienten. Das hat unter anderem den Vorteil,dass man sogar uber beliebigen Korpern oder Ringen arbeiten kann.

Fur einen Ring R, der stets als kommutativ mit Einselement 1 vorausgesetztwird, bezeichne R[[x]] die Menge aller Folgen f = (f0, f1, ...) mit Koeffizientenaus R, also

R[[x]] = RN0 .

Die Teilmenge R[x] aller f ∈ R[[x]], deren Trager {n ∈ N0 | fn 6= 0} endlich ist,besteht dann aus allen Polynomen mit Koeffizienten aus R. Wir betrachten diespeziellen Folgen

ej = (δj,n) = (0, ..., 0, 1, 0, ....)

mit einer 1 an der j-ten Stelle und setzen x0 := e0, x := e1. Ist R ein Korper,so ist R[[x]] offenbar ein R-Vektorraum, und die kanonischen Einheitsvektorenej bilden eine Basis des Unterraums R[x] der Polynome.

100

Im Falle eines beliebigen Ringes R gibt es genau eine uber Summen distribu-tive Multiplikation auf R[x] mit xj = ej fur alle j ∈ N0, namlich das sogenannteCauchy-Produkt (auch Konvolution oder Faltung genannt) mit den Koeffizienten

(fg)n =n∑k=0

fk gn−k =∑k+l=n

fk gl .

Genau so definieren wir das Cauchy-Produkt formaler Potenzreihen und sehen:

Satz 4.2 Die Menge R[[x]] der formalen Potenzreihen wird mit der komponen-tenweisen Addition und dem Cauchy-Produkt zu einem kommutativen Ring mitNullelement 0 = 0x0 und Einselement 1 = x0. Der kleinste Unterring von R[[x]],der x enthalt, ist R[x]. Jedes Polynom f ∈ R[x] hat die eindeutige Darstellung

f =d∑

n=0

fn xn mit d = Grad f = max{k ∈ N0 | fk 6= 0} (= −∞ fur f = 0).

R[[x]] heißt Ring der formalen Potenzreihen und R[x] Polynomring in der Va-riablen x. Elemente r ∈ R identifiziert man mit den Elementen rx0 von R[x]und betrachtet in diesem Sinne R als Unterring von R[x] und R[[x]].

Skeptische Leser mogen fragen, wieso x = e1 eine ”Variable” ist. Unter einerVariablen stellt man sich ja einen ”Platzhalter” vor, fur den man beliebige Werteeines vorgegebenen Bereiches (hier des Ringes R oder eines Oberringes von R)einsetzen kann. Das ist zumindest fur den Polynomring R[x] auch tatsachlichder Fall: Zu jedem Element r eines Oberringes S von R gibt es genau einenRinghomomorphismus von R[x] in S, der die Elemente von R auf sich selbstund x auf r abbildet, namlich den Einsetz-Homomorphismus

f =d∑

n=0

fnxn 7→ f(r) =

d∑n=0

fnrn .

Hierdurch ist R[x] bis auf Isomorphie eindeutig bestimmt. Man kann also fur xirgendein anderes Element eines Oberrings ”einsetzen”; in diesem Sinn ist x undjedes y, fur das die Zuordnung f 7→ f(y) von R[x] in S injektiv ist, als ”Variable”geeignet. Eine ahnliche Charakterisierung ist fur R[[x]] moglich, aber das wurdehier zu weit von unserem Ziel wegfuhren und wird fur unsere kombinatorischenAnwendungen nicht benotigt.

Im Allgemeinen sollte man zwischen Polynomen f und den zugehorigen Po-lynomfunktionen f unterscheiden, die durch Einsetzen von Ringelementen ent-stehen. Zum Beispiel ist f = x2−x nie das Nullpolynom, aber uber dem Korper{0, 1} ist f die Nullfunktion! Ist allerdings R ein Unterring des Korpers C derkomplexen Zahlen, so ist die Zuordnung f 7→ f von R[x] in RR injektiv. Daherschreibt man ublicherweise f(r) statt f(r); mit dieser Konvention ist dann sogarf = f(x). Wir werden zunachst weiter die Elemente von R[[x]] mit f bezeichnen;manchmal wird die Notation f(x) einleuchtender sein.

101

Unter geeigneten Voraussetzungen kann man auch unendliche Summen vonformalen Potenzreihen bilden. Wie nennen eine Folge (fm) von formalen Po-tenzreihen fm = (fm,n | n ∈ N0) summierbar, falls fur jedes n ∈ N0 die Menge

Mn(f) := {m ∈ N0 | fm,n 6= 0}

endlich ist. In diesem Fall ist die koeffizientenweise gebildete Summe

s =∑m

fm =∑m≥0

fm

wohldefiniert, und ihr n-ter Koeffizient ist

sn =∑m

fm,n :=∑

m∈Mn(f)

(fm)n .

In diesem Sinne ist jede formale Potenzreihe f die Summe von Monomen :

f =∑n

fn xn =

∑n≥0

fn xn.

Man kann beim Multiplizieren rechnen, wie man es von Polynomen gewohnt ist:Zur Bildung des n-ten Koeffizienten im Produkt zweier formaler Potenzreihensummiert man die Produkte der Koeffizienten der Faktoren mit Indexsumme n.

Ab jetzt machen wir generell folgende Annahme (die in den wichtigstenFallen R = Z, Q, R oder C sicher erfullt ist):

Fur jedes n ∈ N ist das n-fache Einselement n1 in R invertierbar.

Dadurch stellen wir sicher, dass die fundamentalen kombinatorischen Ausdrucke1n,

1n!

und(n

m

)=

n!m!(n−m)!

in R wohldefiniert sind.

Beispiele 4.3 Produkte geometrischer Reihen

(∑n

xn)(∑n

xn) =∑n

(n+ 1)xn , (∑n

xn)(∑n

(−1)n xn) =∑n

x2n.

Durch Iteration bekommt man eine Formel fur alle naturlichen Potenzen derformalen Potenzreihe

∑xn mittels Binomialkoeffizienten (Beweis induktiv):

(∑n

xn)m =∑n

(n+m− 1m− 1

)xn =

∑n

(n+m− 1

n

)xn.

Die Potenzschreibweise ist bei der Produktbildung erheblich suggestiver als dieFolgenschreibweise, aber nicht alles ”Wohlvertraute” ist hier selbstverstandlich.Wer nur an den rein kombinatorischen Anwendungen interessiert ist, kann dienachsten Seiten bis zum Ende des Abschnitts uberschlagen. Aber Vorsicht!Nicht alle aus der Analysis bekannten Konstruktionen sind uneingeschranktubertragbar – und Konvergenzargumente sind meist nicht zulassig! Besonderswichtig (und beweistechnisch nichttrivial) wird die Kettenregel fur den glied-weisen Differentiationsoperator D sein: D(f ◦ g) = (Df ◦ g)Dg.

102

Exkurs: Rechnen mit formalen Potenzreihen

Eine erste scheinbar offensichtliche Regel ist das ”unendliche Distributivgesetz”:

Lemma 4.4 Ist die Folge (fm) ∈ R[[x]]N0 summierbar, so auch (fm g) fur jedesg ∈ R[[x]], und es gilt∑

m

fm g = (∑m

fm)g .

Beweis. Die Mengen Mn(f) =⋃{Mk(f) | k ≤ n} sind immer noch endlich, und

fur h = (hm) = (fm g) gilt Mn(h) ⊆ Mn(f), denn m 6∈ Mk(f) fur alle k ≤ nimpliziert hm,n =

∑nk=0 fm,k gn−k = 0, d.h. m 6∈Mn(h). Fur s =

∑m fm folgt

(∑m

fm g)n = (∑m

hm)n =∑

m∈Mn(h)

hm,n =n∑k=0

∑m∈Mk(f)

fm,k gn−k

=n∑k=0

sk gn−k = (sg)n = ((∑m

fm)g)n .�

Fur viele kombinatorische Anwendungen besonders hilfreich ist die Inversen-bildung im Ring der formalen Potenzreihen. Sie gelingt erstaunlich oft und aufrecht einfache Weise:

Satz 4.5 Ein Element f ∈ R[[x]] ist genau dann invertierbar in R[[x]], wenn f0

invertierbar in R ist (was in einem Korper schlicht f0 6= 0 bedeutet). In diesemFall berechnet man die Inverse g = 1

f rekursiv durch die Formel

g0 =1f0, gn = − 1

f0

n∑k=1

fk gn−k (n ∈ N).

Denn die linke Gleichung ist aquivalent zu f0 g0 = 1, und die rechte zun∑k=0

fk gn−k = 0 fur n ∈ N .

Beispiele 4.6 Quotienten von formalen Potenzreihen(1) Als formale Potenzreihe existiert 1

x nicht, weil das ”konstante Glied” x0

gleich 0 ist. Dennoch kann man fur jedes f ∈ R[[x]] mit f0 = 0 die formalePotenzreihe g = f

x bilden: Sie hat die um eine Stelle verschobenen Koeffizientengn= fn+1. Analog entsteht fur f ∈ R[[x]] mit fn= 0 fur alle n<m die formalePotenzreihe g = f

xm durch m-fache Indexverschiebung: gn = fn+m.

Umgekehrt ist fur beliebiges g ∈ R[[x]] die formale Potenzreihe f = xmg gegebendurch fn = 0 fur n < m und fn = gn−m fur n ≥ m.

(2) Fur die Polynome 1− x und 1 + x (mit 1 = x0) ergeben sich als Inverse diebekannten geometrischen Reihen:

103

11−x

=∑n

xn ,1

1+x=∑n

(−1)n xn ,1

1−x1

1+x=

11− x2

=∑n

x2n .

Fur konstante Folgen r = (r, r, r, ...) (r ∈ R) hat man die Darstellung r =r

1− x.

Allgemeiner lasst sich fur beliebige formale Potenzreihen f deren summatorischeReihe s mit sn =

∑nk=0 fk darstellen durch

s =f

1− x.

(3) Aus (2) erhalt man fur jedes m ∈ N0 die erzeugende Funktion fur die Anzahlder monotonen Funktionen von n nach m (siehe 4.3 und Satz 1.10):

1(1− x)m

= (∑n

xn)m =∑n

(n+m− 1

n

)xn.

(4) Wegen(z

n

)= (−1)n

(n− z − 1

n

)stimmt die Binomial-Reihenentwicklung

(1 + x)z =∑n

(z

n

)xn

nicht nur fur naturliche Zahlen z, sondern nach (3) sogar fur alle ganzzahligen z.Fur beliebige komplexe Zahlen z nimmt man sie als Definition der linken Seite.

Fur f ∈ C[[x]] kann man die Koeffizienten von f mit Hilfe der Taylorent-wicklung zuruckgewinnen:

fn =1n!

(Dnf)(0),

wobei Dnf die n-te Ableitung von f bedeutet. Brook Taylor (1685 – 1731)war einer der ersten, die systematisch den formalen Umgang mit Potenzreihenuntersuchten. Bekanntlich gilt der folgende wichtige Satz der Analysis:

Satz 4.7 Zu jeder formalen Potenzreihe f = (fn) ∈ C[[x]] gibt es ein eindeuti-ges % ∈ [0,∞] (den Konvergenzradius), so dass die Reihen f(z) =

∑∞n=0 fn z

n

fur |z| < % konvergieren und fur |z| > % divergieren. Ist der Konvergenzradius% > 0, so ist f(z) fur |z| < r unendlich oft differenzierbar, und die Koeffizientenfn sind uber die Gleichung fn = 1

n! (Dnf)(0) festgelegt.

Im Falle % > 0 kann man die durch f(z) = f(z) definierte Funktion f : C→ Cmit Fug und Recht die erzeugende Funktion von f nennen. Wie wir aus derAnalysis wissen, darf man reelle und komplexe Potenzreihen ”gliedweise” dif-ferenzieren und integrieren. Diese Tatsache legt nahe, Differentiation und Inte-gration auch fur formale Potenzreihen einzufuhren:

Fur f = (fn) ∈ R[[x]] seien Df ∈ R[[x]] und If ∈ R[[x]] definiert durch

(Df)n = (n+ 1)fn+1 , (If)0 = 0, (If)n =1nfn−1 fur n ∈ N .

Dann sind die vertrauten Differentiations- und Integrationsregeln erfullt:

104

Satz 4.8 Fur beliebige formale Potenzreihen f, g ∈ R[[x]] gilt:

Df =∑n

n fn xn−1 , If =

∑n

1n+ 1

fn xn+1 ,

D If = f , IDf = f − f0 = f − f0 x0 ,

D(f + g) = Df +Dg , I(f + g) = If + Ig ,

D(r g) = r Dg , I(r g) = r Ig (r ∈ R) ,

f = g ⇐⇒ Df = Dg und f0 = g0 ⇐⇒ If = Ig .

Fur f ∈ C[[x]] ist Df die Ableitung und If eine Stammfunktion von f .

Beispiele 4.9 Exponential- und Logarithmusreihen(1) Die einzigen formalen Potenzreihen, die mit ihrer Ableitung ubereinstimmen,sind die Exponentialreihen

Er := r exp(x) :=∑n

r

n!xn (r ∈ R) ,

was man sofort durch Koeffizientenvergleich erkennt: Die Bedingung f = Df ,d.h. fn = (n+ 1)fn+1 fur alle n ∈ N0, ist aquivalent zu fn = r

n! fur r = f0.

Fur R = R oder C gilt mit Konvergenzradius ∞:

Er(z) = r ez , wobei e =∞∑n=0

1n!.

(2) Eine ”formale Logarithmusreihe” mit Ableitung 1x kann es nicht geben, weil

die formale Potenzreihe x gar nicht invertierbar ist (das ”konstante Glied ver-schwindet”). Jedoch erhalt man durch formales Integrieren der geometrischenReihe 1

1+x =∑n(−1)n xn eine ”um 1 verschobene Logarithmusreihe”

l := I(1

1 + x) = I(

∑n

(−1)n xn) =∑n

(−1)n

n+ 1xn+1 =

∑n≥1

(−1)n−1

nxn .

Uber R stellt l den verschobenen Logarithmus mit Konvergenzradius 1 dar:

l(z) = ln(z + 1) =∫ z

1

11 + t

dt .

Wahrend die Verknupfung f ◦ g von Funktionen eine wohlbekannte Kon-struktion ist, muss man beim Umgang mit einer entsprechenden Kompositionvon formalen Potenzreihen einige Vorsicht und Sorgfalt walten lassen. Die fol-gende Festlegung ist naheliegend: Fur formale Potenzreihen f, g in R[[x]] seif ◦ g ∈ R[[x]] definiert durch

f ◦ g := f(g) :=∑m

fm gm .

105

Aber das ist nur dann fur jedes f ein wohldefinierter Ausdruck, wenn die Folge(gm) summierbar ist! Wie sich gleich herausstellen wird, ist dies genau dann derFall, wenn das ”konstante” Glied der Potenzreihe g verschwindet, d.h. g0 = 0gilt. Denn dann (und nur dann) ist jede der Mengen {m ∈ N0 | gmn 6= 0}endlich, wobei gmn der n-te Koeffizient der m-ten Potenz gm von g bezuglichdes Cauchy-Produkts ist. Er ergibt sich induktiv durch

g0n = x0

n = (e0)n , gmn =n∑k=0

gm−1k gn−k (m ∈ N) .

Lemma 4.10 Fur formale Potenzreihen f, g gilt:

g0 = 0 ⇐⇒ gmn = 0 fur n < m =⇒ gmm = g1m , (f ◦ g)n =

n∑m=0

fm gmn .

Beispiele 4.11 Kompositionen formaler Potenzreihen

(1) Fur jede formale Potenzreihe f gilt f ◦ x = x ◦ f = f .

(2) Es ist stets xm ◦ f = fm, z.B. xm ◦ 11+x =

(1

1+x

)m= 1

(1+x)m .

(3) g = f ◦xm bedeutet gkm = fk und gn = 0 sonst. Nur selten ist f ◦xm = fm.(Wann genau?)

Einige Regeln fur die Komposition ◦ von formalen Potenzreihen erscheinenauf den ersten Blick offensichtlich, doch erweisen sich die exakten Beweise tech-nisch als etwas knifflig. Da die nachfolgenden Fakten haufig unzureichend odergar nicht begrundet werden, fuhren wir die Beweise hier im Detail aus.

Lemma 4.12 Fur jede summierbare Folge (fm) formaler Potenzreihen und je-des h ∈ R[[x]] mit h0 = 0 ist auch die Folge (fm ◦ h) summierbar, und es giltdas Links-Distributivgesetz

(∑m

fm) ◦ h =∑m

(fm ◦ h) .

Beweis. ((∑m fm) ◦ h)n =

∑nk=0(

∑m fm)k hkn =

∑nk=0

∑m fm,k h

kn ,

(∑m fm ◦ h)n =

∑m(fm ◦ h)n =

∑m

∑nk=0 fm,k h

kn =

∑nk=0

∑m fm,k h

kn . �

Das ”Rechts-Distributivgesetz” h ◦ (∑m fm) =

∑m h ◦ fm ist falsch !

Lemma 4.13 Fur beliebige formale Potenzreihen f, g, h∈R[[x]] mit h0 =0 gilt:

(1) (f ◦ h)(g ◦ h) = (fg) ◦ h .

(2) (g ◦ h)m = gm ◦ h .

(3) f ◦ (g ◦ h) = (f ◦ g) ◦ h , falls auch g0 = 0 .

106

Beweis. (1) Wegen hik = hj l = 0 fur k < i und l < j sowie hi+j = hi hj gilt:

((f ◦ h)(g ◦ h))n =∑k+l=n(f ◦ h)k (g ◦ h)l =

∑k+l=n

∑ki=0 fi h

ik

∑lj=0 gj h

jl

=∑nm=0

∑i+j=m fi gj

∑k+l=n h

ik h

jl=∑nm=0

∑i+j=m fi gj h

mn=((fg) ◦ h)n .

(2) folgt induktiv aus (1).

(3) Mit Hilfe von (1), (2) und Lemma 4.12 berechnen wir:

f ◦ (g ◦ h) =∑m fm (g ◦ h)m =

∑fm g

m ◦ h = (∑fm g

m) ◦ h = (f ◦ g) ◦ h . �

Zusammenfassend erhalten wir

Satz 4.14 Die Menge M = xR[[x]] aller formalen Potenzreihen ohne konstan-tes Glied ist bezuglich ◦ ein Monoid mit neutralem Element x.Die Substitutions-Abbildung s : M →MM , f 7→ f mit f(h) = f ◦ h erfullt

(f+g)∼

= f+g, (r f)∼

= r f , (fg)∼

= f g, (f ◦ g)∼

= f ◦ g.

Die letzte Gleichung liefert eine nachtragliche Rechtfertigung fur die Definitionder Komposition ◦ . Im Falle der Korper R oder C wird daruber hinaus beimUbergang von formalen Potenzreihen zu den dargestellten Funktionen aus derabstrakten Komposition ◦ die konkrete Verknupfung von Funktionen:

(f ◦ g)∼

= (∑m

fm gm)

∼=∑m

(fm gm)∼

=∑m

fm gm = f ◦ g .

Die Substitutions-Abbildung s ist nach Satz 4.14 ein Homomorphismus so-wohl bezuglich der Ringoperationen als auch bezuglich der Komposition in demMonoid M . Außerdem ist s injektiv und folglich M isomorph zu einem Un-termonoid von MM mit der Hintereinanderausfuhrung von Abbildungen. Dazuvermerken wir die Kurzungsregel :

Lemma 4.15 Fur f, g ∈ R[[x]] und h ∈ xR[[x]] mit invertierbarem h1 folgt ausf ◦ h = g ◦ h bereits f = g.

Beweis. Aufgrund des Links-Distributivgesetzes (f − g) ◦h = f ◦h− g ◦h (sieheLemma 4.12) genugt es, von f ◦h = 0 auf f = 0 zu schließen. Das geht induktiv:Ist fm = 0 fur alle m < n gezeigt, so folgt 0 = (f ◦ h)n =

∑nm=0 fm h

mn =

fn hnn = fn h1

n, und da h1 invertierbar ist, fn = 0. �

Wieder ist es hilfreich, die invertierbaren Elemente des Monoids M = xR[[x]]zu kennen; sie bilden eine Gruppe bezuglich der Komposition ◦.

Satz 4.16 Ein Element h des Monoids M = xR[[x]] ist genau dann invertierbarbezuglich ◦, wenn h1 invertierbar in R ist. In diesem Fall berechnet sich dieInverse g = h− (nicht zu verwechseln mit 1

h , das nicht existiert) rekursiv mittels

g1 =1h1

, gn = − 1h1n

n−1∑m=1

gm hmn (n > 1).

107

Beweis. Wir setzen G = {h ∈ M | h1 invertierbar in R} und suchen zu h ∈ Gein g ∈ G mit g ◦ h = x. Dann ist notwendigerweise g0 = 0, und zu losen sinddie Gleichungen

(g ◦ h)1 = g1 h1 = 1 , (g ◦ h)n =∑nm=1 gm h

mn = 0 fur n > 1.

Ist h1 und damit auch jedes hnn = h1n invertierbar, so sind die eindeutigen

Losungen dieser Gleichungen offenbar die in Satz 4.16 angegebenen. Umgekehrtfolgt aus der Gleichung g1 h1 = 1 naturlich die Invertierbarkeit von h1 in R.

Wir durfen nicht vergessen, noch die Gleichung h ◦ g = x zu verifizieren (dennin beliebigen Monoiden muss nicht jedes Element mit einem Linksinversen auchein Rechtsinverses haben): Aus g◦h = x folgt (h◦g)◦h = h◦(g◦h) = h◦x = x◦hund daraus mit der Kurzungsregel h ◦ g = x. �

Summen-, Produkt- und Kettenregel, von Leibniz im klassischen Infinite-simalkalkul entdeckt, gelten auch fur formale Potenzreihen:

Satz 4.17 Der Ableitungs-Operator D erfullt folgende Regeln:

(S) Summenregel: D(∑m fm) =

∑mDfm fur summierbare Folgen (fm).

(P) Produktregel: D(fg) = Df g + f Dg fur f, g ∈ R[[x]].

(K) Kettenregel: D(f ◦ g) = (Df ◦ g)Dg fur f ∈ R[[x]] und g ∈ xR[[x]].

Fur einen nullteilerfreien Ring R (z.B. R = R oder C) ist der Ableitungsoperatorder einzige von Null verschiedene Operator auf R[[x]] mit diesen Eigenschaften.

Beweis. (S) Mit (fm) ist auch die Folge (Dfm) summierbar, da Mn(Df) inMn+1(f) enthalten (im Falle R ⊆ C sogar gleich) ist. Es ergibt sich

(D(∑m

fm))n = (n+ 1)(∑m

fm)n+1 =∑m

(n+ 1) fm,n+1 = (∑m

Dfm)n .

(P) Mit Hilfe der Assoziativ-, Kommutativ- und Distributivgesetze erhalten wir

(D(fg))n = (n+1)∑n+1k=0 fk gn+1−k =

∑n+1k=0(k fk gn+1−k + (n+1−k)fk gn+1−k)

=∑nk=0(k+1) fk+1 gn−k +

∑nk=0 fk (n+1−k) gn+1−k

=∑nk=0(Df)k gn−k +

∑nk=0 fk (Dg)n−k = (Df g + f Dg)n .

(K) Unter Ausnutzung von (S), D(r g) = r Dg und 4.12 berechnen wir:

D(f ◦ g)=D(∑m fm g

m)=∑mD(fm gm)=

∑m fmD(gm),

(Df ◦ g)Dg = (∑mmfm x

m−1 ◦ g)Dg =∑mmfm g

m−1Dg .

Es reicht also, die Gleichung D(gm) = mgm−1Dg zu verifizieren, und das gehtinduktiv mittels (P): D(g0) = D(x0) = D(x0x0) = 2D(x0)x0 = 2D(x0) = 0,

D(gm+1) = D(gmg) = D(gm) g+gmDg = mgm−1g Dg+gmDg = (m+1)gmDg.

Sei umgekehrt ein Operator D : R[[x]] −→ R[[x]] mit (S), (P) und (K) gegeben.

108

Aus (P) folgt wie vorher D(x0) = 0. Daraus schließen wir mit (K) fur r ∈ R:D(r x0) = D(r x0 ◦ x0) = (D(r x0) ◦ x0)D(x0) = 0, und dann wieder mit (P):D(r g) = D(r x0 g) = 0 g + r x0Dg = r Dg. Also implizieren (P) und (K) die

Faktorregel: D(rg) = r Dg fur r ∈ R und g ∈ R[[x]].

Daraus ergibt sich unter Einbeziehung von (S):

Df = D(∑n fn x

n) =∑n fnD(xn).

Die Nullteilerfreiheit von R und die Kettenregel erzwingt Dx = εx0 (ε ∈ {0, 1}):Angewandt auf f=g=x ergibt (K) Dx = D(x ◦x) = (Dx ◦x)Dx = (Dx)2. Dieeinzigen Potenzreihen h mit h = h2 sind aber 0 und x0, denn es muss gelten:h0 = h0

2, also h0(h0 − 1) = 0 und daher h0 ∈ {0, 1}; in jedem Fall folgt aushk = 0 fur 0 < k < n: hn = h2

n =∑nk=0 hk hn−k = 2h0hn, also hn = 0.

Mit (P) folgt schließlich induktiv D(xn) = ε nxn−1, Df = ε∑n n fnx

n−1. �

Folgerung 4.18 Formale Potenzreihen f mit f0 = 0 und invertierbarem Ko-effizienten f1 sind invertierbar bezuglich ◦, und es gilt die Inversionsregel:

D(f−) =1

Df ◦ f−.

Denn nach der Kettenregel ist ja 1 = Dx = D(f ◦ f−) = (Df ◦ f−)D(f−) .

In der Praxis lasst sich die Tatsache, dass g kompositionsinvers zu f ist, oftleicht durch f0 = g0 = 0 und folgende Differentialgleichung beweisen:

(Df ◦ g)Dg = 1 ( = x0).

Denn letztere bedeutet nach der Kettenregel D(f ◦ g) = 1, was wegen f0 = 0 zuf ◦ g = x aquivalent ist, und hDg = 1 erzwingt die Invertierbarkeit von g1.

Beispiel 4.19 Inverse von PolynomenWir bestimmen fur jedes m ∈ N die Kompositionsinverse w zum Polynom

p = (1 + x)m − 1 =∑n≥1

(m

n

)xn (p0 = 0, p1 = m).

Die Differentialgleichung

1 = D(p◦w) = D((1+w)m−1) = m (1+w)m−1Dw = m (1+w)mDw1+w = m(1+x)Dw

1+w

bedeutet m(1 + x)Dw = 1 + w . Koeffizientenvergleich ergibt die Rekursionm(n+1)wn+1 +mnwn = wn, wn+1 = 1

n+1 ( 1m − n)wn und induktiv wn =

(1/mn

).

Damit erhalten wir, wie erwartet, die formale Wurzel-Potenzreihe

w = (1 + x)1/m − 1 =∑n≥1

(1/mn

)xn mit p ◦ w = ((1 + x)1/m)m − 1 = x.

109

Um alle gelaufigen Regeln fur Exponentiation und Logarithmierung von(fast) beliebigen Potenzreihen sicher zu stellen, mussen wir zwei fundamentalePotenzreihen naher unter die Lupe nehmen. Die formale Exponentialreihe

exp(x) :=∑n

1n!xn

hat kein Inverses bezuglich Komposition, weil das ”konstante Glied” 1/0! = 1nicht verschwindet. Hingegen ist h = exp(x)−1 kompositionsinvers zur formalenLogarithmusreihe (siehe 4.9)

l(x) =∑n≥1

(−1)n−1

nxn ,

wie sich sofort durch Ableiten ergibt (die ”konstanten Glieder” verschwinden):

D(l ◦ h) = (Dl ◦ h)Dh = (1

1 + x◦ h) (1 + h) =

1 + h

1 + h= 1 .

Beginnt man jedoch mit D(h ◦ l), kommt man nicht voran:

D(h ◦ l) =(1 + h) ◦ l

1 + x=?

Dennoch wissen wir aus fruheren Uberlegungungen (siehe Beweis von Satz 4.16),dass auch h ◦ l = x gelten muss. Wieder haben wir die Inversionsgleichungenmit Hilfe der Kettenregel sehr schnell herleiten konnen, wahrend ein direkterBeweis mittels Koeffizientenvergleich ziemlich muhselig ware.

Fur r ∈ R sei R[[x]]r die Menge der formalen Potenzreihen mit f0 = r.Die komponierte Potenzreihe

exp(f) := exp(x) ◦ f =∑n≥0

1n!fn

ist fur jedes f ∈ R[[x]]0 definiert und liegt wegen f0 = x0 = 1 in R[[x]]1.

Andererseits ist fur jedes g ∈ R[[x]]1 die formale Potenzreihe

log(g) := l ◦ (g − 1) =∑n≥1

(−1)n−1

n(g − 1)n

wohldefiniert und liegt in R[[x]]0. Und aufgrund der oben hergeleiteten Glei-chungen l ◦ h = x und h ◦ l = x wissen wir:

Lemma 4.20 Die Abbildung exp : R[[x]]0 → R[[x]]1 ist invers zur Abbildunglog : R[[x]]1 → R[[x]]0. Mit anderen Worten: Fur f ∈R[[x]]0 und g ∈R[[x]]1 gilt

g = exp(f) ⇐⇒ f = log(g) .

110

Fur jedes f ∈ R[[x]] und n ∈ N ist der verallgemeinerte Binomialkoeffizient(f

n

):=

(f)nn!

=1n!f(f−1)...(f−n+1) wie auch

(f

0

)= 1

wohldefiniert, und wir konnen mit Hilfe der Binomial-Reihenentwicklung belie-bige Potenzen g f fur f ∈ R[[x]] und g ∈ R[[x]]1 bilden:

g f := (1 + (g−1)) f =∑n

(f

n

)(g−1)n .

(Die Folge ist summierbar wegen g − 1 ∈ R[[x]]0.)

Lemma 4.21 Fur r ∈ R sowie f ∈ R[[x]]0 und g ∈ R[[x]]1 gilt

D((1 + x)r) = r (1 + x)r−1 , D(gr) = r g r−1Dg ,

D(exp(f)) = exp(f)Df , D(log(g)) =1gDg .

Beweis. Zuerst berechnet man

D((1+x)r) = D(∑n

(rn

)xn) =

∑n(n+1)

(rn+1

)xn = r

∑n

(r−1n

)xn = r (1+x)r−1 .

Die restlichen drei Ableitungen bekommt man sofort mit der Kettenregel. �

Sehr nutzlich sind die folgenden Regeln fur Summen, Produkte und Potenzen:

Satz 4.22 Fur alle formalen Potenzreihen f, h ∈ R[[x]]0 und g, k ∈ R[[x]]1 gilt:

(1) log(g k) = log(g) + log(k) (2) log(g f ) = f log(g)

(3) exp(f h) = exp(f)h (4) g f = exp(f log(g))

(5) g f+h = g f gh (6) gh k = (gh)k

(7) (g + h) f =∑n

(fn

)gf−n hn (8) (g k) f = g f k f

Beweis. (1) Wegen gk ∈ R[[x]]1 und log(gk), log(g), log(k) ∈ R[[x]]0 genugt es,die Gleichheit der Ableitungen zu zeigen:D log(gk) = 1

gk (g Dk + kDg) = Dgg + Dk

k = D(log(g) + log(k)).

(2) Wir betrachten die formalen Potenzreihen log((1 + x)y) und y log(1 + x)in zwei Variablen x und y. Beide liegen in R[[y]][[x]]0, so dass ihre Gleichheitwieder zu der ihrer Ableitungen nach x aquivalent ist, und die sieht man so:

Dx(log(1 + x)y) = 1(1+x)y y (1 + x)y−1 = y

1+x = Dx(y log(1 + x)).(Die Gleichung (1 + x)y = (1 + x)y−1(1 + x) folgt aus

(yn

)=(y−1n−1

)+(y−1n

).)

Substitution von f−1 fur x und g fur y in log((1+x)y) = y log(1+x) gibt (2).

(3), (4) und (6) resultieren mit Lemma 4.20 unmittelbar aus (2), und (5) folgtaus (1) und (2): log(g f+h) = (f + h) log(g) = log(gf ) + log(gh) = log(g f gh).Analog folgert man (8) aus (1) und (2).

(7) g ∈ R[[x]]1 ist invertierbar, und es gilt g+h = g(1+ hg ) ∈ R[[x]]1, hg ∈ R[[x]]0.

Mit (6) und (8) folgt (g+h) f = g f (1+hg ) f = g f

∑n

(fn

)(hg )n =

∑n

(fn

)g f−nhn.

�

111

4.2 Exponentiell erzeugende Funktionen

Bei vielen Anzahlformeln erweist sich eine Modifikation der erzeugenden Funk-tionen als sinnvoll und nutzlich: Zu jeder Folge (bzw. formalen Potenzreihe)f ∈ R[[x]] hat man die exponentielle Potenzreihe bzw. die durch sie dargestellteexponentiell erzeugende Funktion

Ef =∑n

fnn!xn .

Insbesondere gilt fur die konstante Folge 1 = (1, 1, 1, ...):

E1 = E(1

1− x) = exp(x) .

Exponentielle formale Potenzreihen haben mehrere eklatante Vorteile. Wirerwahnten schon, dass fur viele kombinatorisch relevante Potenzreihen der Kon-vergenzradius 0 ist, ihre Koeffizienten also nicht aus analytischen Funktionen ge-wonnen werden konnen. Der Konvergenzradius laßt sich aber durch Ubergangzur entsprechenden exponentiellen Potenzreihe haufig deutlich verbessern. Inder Taylorentwicklung einer analytischen Funktion

g(z) =∑n

1n!

(Dng)(0) zn

bilden zudem die Glieder fn = (Dng)(0) eine Folge f mit Ef(z) = g(z), undumgekehrt impliziert diese Geichung die obige Taylorentwicklung.

Beispiele 4.23 Konvergenzradien exponentiell erzeugender Funktionen(1) Fur die Fakultaten fn = n! konvergiert die Potenzreihe f =

∑n n!xn in

keinem Punkt von C außer 0. Hingegen ist die Potenzreihe Ef =∑n x

n einfachdie geometrische Reihe, welche uber C die Funktion 1

1−x mit Konvergenzradius1 darstellt.

(2) Die Anzahl der Baume (trees) mit einer festen n-elementigen Knotenmengeist nach Cayley gleich tn = nn−2. Die zugehorige Potenzreihe t hat wiederKonvergenzradius 0, wogegen die exponentielle Potenzreihe Et =

∑nnn−2

n! xn

den Konvergenzradius 1/e hat. (Wie sieht man das? Tipp: Lemma 4.54.)Auf die durch die Reihe Et dargestellte Funktion kommen wir noch zuruck.

(3) Fur festes r ∈ R ist die exponentiell erzeugende Funktion der fallendenFaktoriellen (r)n = r(r−1)...(r−n+1) die Binomialreihe∑

n

(r

n

)xn = (1 + x)r mit Konvergenzradius 1 uber C .

(4) Fur die Anzahlen gn = 2n(n−1)/2 aller Graphen oder hn aller Halbordnungenauf n-elementigen Mengen haben leider auch die exponentiellen Potenzreihen Egund Eh noch den Konvergenzradius 0; denn wegen gn ≥ hn ≥ 2bn

2/4c gilt

limn→∞

gnn!zn = lim

n→∞

hnn!zn =∞ fur jedes feste z ∈ C .

In diesen Fallen muss man also weiter mit formalen Potenzreihen arbeiten.

112

Da wir in der Kombinatorik vorrangig gewisse Strukturen auf n-elementigenMengen zahlen wollen, prazisieren wir diesen Begriff folgendermaßen: EineStrukturklasse ist eine Klasse S von Mengen zusammen mit einer Funktion,die jedem S aus S eine Menge X = |S| zuordnet; wir nennen dann S eine (S)-Struktur auf X und X die Grundmenge der Struktur. Weiter fordern wir, dassdie Anzahl der S-Strukturen auf einer n-elementigen Menge X nur von n, nichtaber von der gewahlten Menge X abhangt. Das ist bei fast allen Strukturen inder Mathematik der Fall. Beispiele sind Digraphen, Graphen oder Ordnungen(X,R), aber auch Permutationen σ : X → X, topologische Raume (X, τ) mitτ ⊆ PX, Halbgruppen G = (X, ·), Ringe R = (X,+, ·, 0, 1) etc.; in all diesenFallen ist X die jeweilige Grundmenge.

Wir studieren im Folgenden, wie man ”zusammengesetzte” Strukturenzahlen kann. Dabei werden sich exponentiell erzeugende Funktionen als her-vorragendes Hilfsmittel erweisen.

Die Kombination zweier Folgen f und g ist die Folge f ♦ g mit den Gliedern

(f ♦ g)n =n∑k=0

(n

k

)fk gn−k .

Das Cauchy-Produkt zweier exponentieller formaler Potenzreihen lasst sich da-mit sehr einfach ausdrucken:

Lemma 4.24 Die exponentiell erzeugende Funktion der Kombination zweierFolgen ist das Cauchy-Produkt der beiden exponentiell erzeugenden Funktionen:

E(f ♦ g) = Ef · Eg .

Denn es ist ja gerade

(f ♦ g)nn!

=n∑k=0

fkk!

gn−k(n−k)!

.

Die kombinatorische Bedeutung dieser weiteren Verknupfung ♦ von Folgenergibt sich aus einer elementaren Beobachtung:

Lemma 4.25 Es seien S und T Strukturklassen; fn sei die Anzahl der S-Strukturen und gn die der T-Strukturen auf einer n-elementigen MengeX.Dann ist (f ♦ g)n die Anzahl der Paare (S, T ), wobei S eine S-Struktur, T eineT-Struktur und X die disjunkte Vereinigung der Grundmengen |S| und |T | ist.

Beweis. Es gibt(nk

)Moglichkeiten, eine k-elementige Teilmenge Y von X aus-

zuwahlen, und dazu fk S-Strukturen auf Y sowie gn−k T-Strukturen auf X \Y ,die man paarweise miteinander kombinieren kann. Durch Summation uber kfolgt die Behauptung. �

113

Beispiel 4.26 Ketten und AntikettenEine Kette ist eine linear geordnete Menge, wahrend eine Antikette eine durchdie Gleichheitsrelation geordnete Menge ist. Wir suchen die Anzahl vn allergeordneten Mengen mit n-elementiger Grundmenge X, die Vereinigung einerKette und einer Antikette sind. Die Anzahl der Ketten mit Grundmenge X istkn = n!, die der Antiketten an = 1. Die Anzahl der Paare (S, T ), bestehendaus einer Kette S und einer Antikette T mit Grundmengen, deren disjunkteVereinigung X ergibt, ist dann

n∑k=0

(n

k

)k! =

n∑k=0

(n)k ,

und die exponentiell erzeugende Funktion hierfur ist

(∑n

n!n!xn)(

∑n

1n!xn) =

ex

1− x.

Das liefert aber noch nicht genau die gesuchten Anzahlen, sondern wir mussendie Falle abziehen, die mehrfach gezahlt wurden: das sind die Paare (S, T ), woS eine einelementige Kette und folglich die disjunkte Vereinigung von S undT die einzige Antikette mit Grundmenge X ist. Diese haben wir n mal zu oftgezahlt, mussen also n abziehen:

vn = 1 +n∑k=2

(n)k , Ev(x) = ex(1 +x2

1−x) = (1 +x+

x2

2+...)(1+x2+x3+...)

n 1 2 3 4

Ordnungen b b b bb b b b b bb bbb b b b b b b bb b bbb bbbb

(n)k , k 6= 1 1 1 2 1 6 6 1 12 24 24

vn 1 3 13 61∑nk=0(n)k 2 5 16 65

Die in Kapitel 1 (siehe Satz 1.12) gefundene Binomial-Inversion erscheintim Lichte exponentiell erzeugender Funktionenen fast trivial:

Satz 4.27 Fur beliebige f, g ∈ RN0 sind folgende sechs Gleichungen aquivalent:

(1a) gn =n∑k=0

(n

k

)fk (n ∈ N0) (1b) fn =

n∑k=0

(n

k

)(−1)n−kgk (n ∈ N0)

(2a) g = f ♦ 11− x

(2b) f = g♦ 11 + x

(3a) Eg(x) = Ef(x) exp(x) (3b) Ef(x) = Eg(x) exp(−x)

114

Beweis. Die Aquivalenzen (1a)⇔ (1b) und (1b)⇔ (2b) gelten nach Definition.(2a)⇔ (3a) und (2b)⇔ (3b) folgen aus Lemma 4.24. Und (3a)⇔ (3b) ist klarwegen exp(−x) = exp(x)−1. �

Eine Struktur S heißt unzerlegbar (oder zusammenhangend), falls sie sichnicht als disjunkte Vereinigung von nichtleeren echten Teilstrukturen darstellenlasst (dabei bezieht sich ”disjunkte Vereinigung” auf die jeweiligen Grundmen-gen). Zusammenhangende Relationen und Graphen haben wir schon kennenge-lernt, zusammenhangende topologische Raume sind ein anderes Beispiel. Untereiner Zerlegungsklasse verstehen wir eine Strukturklasse S mit der Eigenschaft,dass jede S-Struktur mit endlicher Grundmenge eine eindeutige Zerlegung inunzerlegbare S-Strukturen (die Komponenten) besitzt, und umgekehrt die dis-junkte Vereinigung von endlich vielen endlichen S-Strukturen wieder eine solcheliefert. Auch hierfur haben wir schon etliche Beispiele kennen gelernt.

Zerlegungsklasse Anzahl an unzerlegbare Strukturen Anzahl cn

Mengen 1 einpunktige Mengen δn,1

Permutationen n! Zykel (n−1)!

Partitionen ΣmSn,m Blocke 1− δn,0Digraphen 2n

2zusammenhangende Digraphen ?

Graphen 2n(n−1)/2 zusammenhangende Graphen ?

Ordnungen ? zusammenhangende Ordnungen ?

Walder ? Baume nn−2

Wurzelwalder (n+1)n−1 Wurzelbaume nn−1

Wir kommen zu einem der schonsten Satze uber erzeugende Funktionen.

Satz 4.28 Es sei S eine Zerlegungsklasse, sowie

an die Anzahl der Strukturen auf einer n-elementigen Menge,

cn die entsprechende Anzahl der unzerlegbaren Strukturen,

c(m)n = cn,m die Anzahl der Strukturen mit genau m Komponenten.

Dann gilt fur die exponentiell erzeugenden Funktionen:

Ec(m) =1m!

(Ec)m , Ea = exp(Ec) , Ec = log(Ea) , DEa = EaDEc .

Beweis. Vorab vermerken wir die Gleichungen cn,0 = δn,0, cn,1 = cn. Es gibtnamlich keine unzerlegbare Struktur mit leerer Grundmenge (da ∅ =

⋃∅).

Aus Lemma 4.25 folgern wir induktiv

Ec(m) =1m!

(Ec)m .

115

Denn diese Formel gilt definitionsgemaß fur m = 1 (und auch fur m = 0); ausder Richtigkeit fur m folgt die fur m+ 1, denn 1

m! (Ec)m+1 = Ec(m) ·Ec ist die

exponentiell erzeugende Funktion fur bn, die Anzahl der Paare (S, T ), wobei Seine Struktur mit genau m Komponenten, T eine mit nur einer Komponente undn die disjunkte Vereinigung der Grundmengen von S und T ist. Nach Definitioneiner Zerlegungsklasse ist die entsprechende ”Vereinigung” der Strukturen wie-der eine S-Struktur, hat m+1 Komponenten, und jede solche entsteht auf dieseWeise m+1 Mal (da die Anordnung der Komponenten ja keine Rolle spielt).Daher lieft Division durch m+1 die behauptete Gleichung fur m+1 statt m.

Die Gleichung Ea = exp(Ec) ergibt sich nun durch Summation uber m, undEc = log(Ea) folgt hieraus mit Lemma 4.20. Differentiation und Kettenregelfuhren schließlich auf DEa = EaDEc. �

Liest man die obigen Gleichungen fur die exponentiell erzeugenden Funktio-nen koeffizientenweise, so gelangt man zu

Folgerung 4.29 Unter den Voraussetzungen von Satz 4.28 gilt

an =n∑

m=1

(n−1m−1

)cm an−m , cn = an −

n−1∑m=1

(n−1m−1

)cm an−m ,

an = n!∑ n∏

k=1

1mk!

(ckk!

)mk, cn = n!

n∑r=1

(−1)r−1

r!

∑ r∏k=1

amkmk!

,

wobei im ersten Fall uber alle (m1, ...,mn) ∈ Nn0 mit

∑nk=1 k ·mk = n und

im zweiten Fall uber alle (m1, ...,mr) ∈ Nn0 mit

∑nk=1mk = n summiert wird.

Dies ist offenbar eine Verallgemeinerung der in Satz 2.37 aufgestellten Glei-chungen fur zusammenhangende Digraphen.

Beispiel 4.30 Wurzelbaume und WurzelwalderDie exponentiell erzeugende Funktion fur die Anzahlen wn = nn−1 der Wur-zelbaume mit n Knoten ist

w(x) =∑n

nn−1

n!xn ,

und die der Wurzelwalder ist

ew(x) =∑n

(n+1)n−1

n!xn =

1x

∑n≥1

nn−1

n!xn =

w(x)x

.

Wir erhalten damit die wichtige Funktionalgleichung

x = w(x) e−w(x) ,

d.h. w(x) ist kompositionsinvers zu x e−x.

116

Viele Anzahlformeln hangen von zwei (oder mehr) Parametern ab; typi-sche Beispiele sind Binomialkoeffizienten und Stirling-Zahlen. In solchen Fallenbraucht man formale Potenzreihen in zwei Variablen, also Elemente der Ringe

R[[x, y]] ' R[[x]][[y]] ' R[[y]][[x]] etc.

Beispiel 4.31 Binomial-DoppelfolgenFur festes m ∈ N ist die Reihe

bm(x) =∑n

(n

m

)xn

in allen Punkten aus C konvergent, weil (n)m ≤ nm viel langsamer als zn furjedes feste z ∈ C wachst. Wir finden die exponentiell erzeugende Funktion

Ebm(x) =1m!

∑n≥m

1(n−m)!

xn =1m!

∑n≥0

1n!xn+m =

xm

m!ex ,

und damit die ”halbexponentiell” erzeugende Funktion in zwei Variablen x, y

fur die Doppelfolge bn,m =(n

m

)der Binomialkoeffizienten:

Eb(x, y) =∑m

∑n

1n!

(n

m

)xn ym =

∑m

xm

m!ym ex = exy ex = ex+xy .

Im Vergleich dazu die doppelte formale Potenzreihe fur Binomialkoeffizienten:

b(x, y) =∑m,n

(n

m

)xn ym =

∑n

xn(1+y)n =∑n

(x+xy)n =1

1−x−xy,

durch die die Exponentialgleichung in Satz 4.28 bestatigt wird:

Eb(x, y) = E(1

1−x−xy) = ex+xy .

Die Potenzreihe fur1

1−x−xyerhalt man auch noch auf andere Weise:

∑n

(n

m

)xn =

∑n

(n)mm!

xn =∑n

Dm(xn)xm

m!= Dm(

11− x

)xm

m!,

b(x, y) =∑m,n

(n

m

)xn ym =

∑m

Dm(1

1− x)

(xy)m

m!=

11−x−xy

.

Die letzte Gleichung ist so zu verstehen: Man bildet die Taylorentwicklung von1

1−x−zin der Variablen z und setzt dann xy fur z ein:

11−x−z

=∑m

Dzm(

11−x−z

)(0)zm

m!=∑m

Dm(1

1−x)zm

m!.

117

Haufig sind ”halbexponentielle Doppelreihen” der Form∑n,m

fn,mm!

xn ym

besonders praktisch. Wir verdeutlichen das an einigen typischen Situationen.

Folgerung 4.32 Mit den Bezeichnungen von Satz 4.28 gilt fur die halbexpo-nentielle Doppelreihe

Ec(x, y) =∑n,m

cn,mm!

xn yn

= exp(Ec(x) y) = exp(y log Ea(x)) = (Ea(x))y .

Beispiel 4.33 Mengen als StrukturenDer einfachste Fall einer Zerlegungsklasse ist der der Mengen (aufgefasst alsStrukturen); die unzerlegbaren Mengen sind die einpunktigen. Somit gilt:

an = 1 , cn = δn,1 , Ec(x) = x , Ea(x) = ex,

Ec(x, y) =∑m

1m!

xm ym = exy = (ex)y .

Beispiele 4.34 Stirling-Zahlen(1) Wir betrachten die Zerlegungsklasse der Permutationen. Hier ist an = n!,und cn,m gibt die Anzahl der Permutationen von n mit m Zykeln (d.h. Kom-ponenten) an, ist also gleich der Stirling-Zahl erster Art sn,m. Insbesondere istcn = cn,1 = sn,1 = (n−1)! die Anzahl der Zykel der Lange n. In diesem Fallergeben sich die Potenzreihen

Ec(x) =∑n

xn

n= − log(1− x) , Ea(x) =

∑n

xn =1

1− x,

Es(x, y) =∑n,m

sn,mm!

xn ym =∑m

1m!

(− log(1−x))mym = e−y log(1−x)

= (1−x)−y =∑n

(−y)nn!

(−1)n xn ,

was die Koeffizientendarstellung der fallenden Faktoriellen durch Stirlingzahlenerster Art (Satz 1.18) bestatigt.

(2) Nehmen wir stattdessen die Zerlegungsklasse der Partitionen (bzw. Aqui-valenzrelationen), so ist cn,m die Anzahl der Partitionen von n in m Blocke, alsodie Stirlingzahl zweiter Art Sn,m. Insbesondere ist cn = δn,0 fur n > 0 gleich 1(es gibt nur eine Partition mit einem Block). Jetzt erhalten wir

Ec(x) =∑n≥1

xn

n!= ex − 1 , Ea(x) = ee

x−1 ,

ES(x, y) =∑n,m

Sn,mm!

xn ym =∑m

1m!

(ex − 1)m ym = e(ex−1)y .

118

4.3 Rekursionen

Viele konkrete Probleme der Kombinatorik beginnen mit der Aufstellung einerRekursionsgleichung fur die gesuchten Anzahlen. Bei einigen kombinatorischenFolgen haben wir solche Rekursionen schon kennengelernt und diese in manchenFallen in explizite Formeln aufgelost. In anderen Fallen ist das nicht gelungenoder hat keine rechnerischen Vorteile gebracht. Wir werden jetzt sehen, dasshaufig die Methode der erzeugende Funktionen (bzw. formalen Potenzreihen)zu eleganten Losungen fuhrt.

Beispiel 4.35 HyperwurfelDer n-dimensionale Hyperwurfel Wn = (2n, En) hat die endlichen 0–1–Folgen(a1, ..., an) ∈ 2n als Ecken, und zwei solche Ecken sind durch eine Kante ver-bunden, wenn sie sich in genau einer Koordinate unterscheiden.

c@@@ ���

000

c���001

c@@@ ���

010

c@@@100

c���011 c101 c@@@ 110

c111

c@@@ ���

���������

���������

���������

0000

c������������

���������

���������

0001

c@@@ ���

���������

���������

���������

0010

c@@@ ���������

���������

���������

0100

c������������

���������

���������

0011 c���������

���������

���������

0101 c@@@ ���������

���������

���������

0110

c���������

���������

���������

0111

c@@@ ���

1000

c���1001

c@@@ ���

1010

c@@@1100

c���1011 c1101 c@@@ 1110

c1111

Die Eckenzahl ist dann naturlich 2n. Das fur diesen simplen Fall etwas bom-bastisch wirkende Rekursionsargument soll nur die Losungsmethode mit Hilfeerzeugender Funktionen klar machen: Da jeder Vektor in 2n sich auf genauzwei Weisen zu einem in 2n+1 erganzen lasst, ist die Eckenzahl vn+1 von Wn+1

doppelt so groß wie die von Wn:

vn+1 = 2vn mit dem Startwert v0 = 1 .

Die erzeugende Funktion erfullt die Gleichung

v =∑n

vn xn = 1 +

∑n

vn+1 xn+1 = 1 + x

∑n

vn+1 xn = 1 + 2xv

mit der erwarteten Losung

v =1

1− 2x=∑n

2n xn .

119

Jetzt fragen wir nach der Kantenzahl kn des n-dimensionalen Hyperwurfels.Hier ist die Losung nicht ganz so offensichtlich. Der Hyperwurfel Wn+1 entstehtaus Wn durch Verdoppelung. Zu den Kanten von Wn und des verschobenenHyperwurfels W ′n kommen die 2n ”parallelen” Verbindungskanten zwische jeeiner alten und einer neuen Ecke hinzu (siehe Diagramm). Das bedeutet

kn+1 = 2 kn + 2n mit dem Startwert k0 = 0

bzw. fur die erzeugende Funktion:

k =∑n

knxn =

∑n

kn+1xn+1 = 2x

∑n

knxn + x

∑n

2nxn

= 2xk +x

1− 2x.

Die Losung ergibt sich am einfachsten mittels Differentiation:

k(x) =x

(1− 2x)2=x

2D(

11− 2x

) =x

2

∑n

n 2n xn−1 =∑n

n 2n−1xn .

Summation uber die Eckengrade bestatigt diese Gleichung:

kn =12

∑x∈2n

d(x) =n

22n .

Beispiel 4.36 Fibonacci-RekursionenDie vielleicht beruhmteste Rekursion ist die der Fibonacci-Zahlen:

fn+2 = fn+1 + fn .

Man begegnet ihr zum Beispiel bei der Frage, auf wieviele Weisen Dominosteinein eine Schachtel passen, deren eine Kantenlange gleich der eines Dominosteinesist, wahrend die andere das n-Fache der Breite eines Dominosteines betragt.

Offenbar gilt fur die gesuchten Anzahlen die obige Rekursion (wobei f0 = 1 hierein etwas gewaltsamer, aber praktischer Startwert ist).

Umformuliert in die Sprache der erzeugenden Funktionen lautet die Rekursion

f =∑n

fnxn = f0 + f1x+

∑n

fn+2 xn+2 = f0 + (f1−f0)x+ (x+ x2)f

oder aufgelost nach f :

f =f0 + (f1−f0)x

1− x− x2.

Um dies in Reihen zu entwickeln, braucht man die Faktorisierung des Nenners:

1− x− x2 = (1− Φx)(1 + φx) ,

120

wobei Φ und φ die beiden Werte des Goldenen Schnitts sind:

Φ− φ = 1 = Φ · φ , Φ =√

5 + 12

, φ =√

5− 12

, Φ + φ =√

5 .

bb

bb

bbb

bb

TTTTT

"""""""""

����� 1

11

φφ

Φ√5

Nun berechnet man die Koeffizienten a und b der Partialbruchzerlegung

f =f0 + f1x

1− x− x2=

a

1− Φx+

b

1 + φx

mittels Koeffizientenvergleich und erhalt fur beliebige Startwerte f0 und f1:

a =f0 Φ + f1√

5, b =

f0 φ− f1√5

.

Schließlich findet man durch Entwicklung der beiden geometrischen Reihen diefolgende, ebenso einfache wie erstaunliche explizite Darstellung:

fn = aΦn + b (−φ)n .

Im klassischen Spezialfall F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn wird a = 1/√

5und b = −1/

√5, und wir gelangen zur beruhmten Formel von Binet:

Fn =1√5

(Φn − (−φ)n) .

Wegen φ < 1 ist Fn stets die ganzzahlige Rundung von Φn/√

5. Der Anfang derFibonacci-Folge sieht so aus:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Die Dominostein-Folge f=Fn+1 beginnt bei f0 = 1. Zwei andere interessanteStartwerte sind L0 = 2, L1 = 1. Sie liefern die sogenannten Lucas-Zahlen Lnmit

Ln+2 = Ln+1 + Ln ,

benannt nach dem Mathematiker Edouard Lucas, der 700 Jahre nach Fibonaccisolche Rekursionen u.a. fur Primzahltests nutzte. Explizit gilt

Ln = Fn+1 + Fn−1 = Φn + (−φ)n .

Die ersten Glieder der Lucas-Folge lauten

2, 1, 3, 4, 7, 11, 18, 39, 57, ...

121

Aufgrund der Rekursionsvorschrift fn+2 = fn+1 + fn ist klar, dass bei ganzzah-ligen Startwerten f0 und f1 auch alle anderen Folgenglieder fn ganzzahlig sind.Sieht man das der expliziten Formel an? Binomialentwicklung zeigt

fn =1√5

((f0Φ + f1)Φn − (−f0φ+ f1)(−φ)n)

=f0√

5

(1 +√

52

)n+1

−

(1−√

52

)n+1+

f1√5

((1 +√

52

)n−

(1−√

52

)n)

=f0

2n∑k

(n+ 12k + 1

)5k +

f1

2n−1

∑k

(n

2k + 1

)5k .

Das ist zumindest ein rationaler Ausdruck – aber dass sich die Zweierpotenzenim Nenner wegkurzen, ist keineswegs offensichtlich! Speziell erhalten wir

Fn =1

2n−1

∑k

(n

2k + 1

)5k , Ln =

12n−1

∑k

(n

2k

)5k ,

und allgemein ergibt sich jede Folge fn mit fn+2 = fn+1 + fn sofort aus derFibonacci-Folge mittels

fn = f0 Fn+1 + (f1−f0)Fn .

Fibonacci-Folgen findet man in vielfaltigster Weise in der Natur realisiert, insbe-sondere bei Bluten- und Fruchtstanden. Bei Kiefernzapfen und Ananasfruchtenzahlt man beispielsweise 5, 8 und 13 Spiralen, bei den Korbchenbluten einerSonnenblume meist 34 und 55 Spiralen!

Beispiel 4.37 Facher und RaderEin Rad mit n ”Speichen” ist ein Graph mit n + 1 Knoten, von denen einer(das Zentrum) Grad n und alle anderen Grad 3 haben. Durch Entfernen einerAußenkante entsteht ein Facher mit n ”Speichen”.

sss sss ss s���

@@@

aa !!

!! aa

LL

��

��

LL sss s

ss ss s���

@@@

aa !!

!! aa

LL

��

LL s s

ss�� sQQs sJJs s@

@@

���

aaaa

!!!!

LLLL

����

�� XX

CC

'

Um die Anzahl fn der Spannbaume eines Fachers zu berechnen, kann man denDeterminantensatz 3.37 fur die Laplace-Matrix benutzen, was durch Entwick-lung nach der ersten Zeile und Spalte auf eine Rekursion fur fn (mit f0 = f1 = 1)fuhrt. Einfacher und anschaulicher ist ein direktes Argument: Man fixiert in ei-nem Facher mit n+3 Knoten eine Speiche s und eine benachbarte Kante k.

s

ks sss�� sQQs sJJs s@

@@

���

aaaa

!!!!

LLLL

����

�� XX

CC

s

ks sss�� sQQs sJJs s@

@@

���

aaaa

!!!!

LLLL

����

�� XX

s

ks sss�� sQQs sJJs s@

@@

���

aaaa

!!!!

LLLL

����

�� XX

CC

s

ks sss�� ss sJJs s@

@@

aaaa

LLLL

����

�� XX

CC

122

Es gibt dann

fn+1 Spannbaume, die s, aber nicht k enthalten,

fn+1 Spannbaume, die k, aber nicht s enthalten,

fn + fn−1 + ...+ f1 + f0 Spannbaume, die sowohl s als auch k enthalten.

Daraus resultiert die Rekursionsgleichung

fn+2 = 2 fn+1 + fn + fn−1 + ...+ f1 + f0 ,

und indem man diese fur fn+1 statt fn+2 einsetzt, vereinfacht man sie zu

fn+2 = 3 fn+1 − fn .

Mit dem gleichen Verfahren wie zuvor findet man

f =f0 + (f1 − 3f0)x

1− 3x+ x2=

a

1− Φ2x+

b

1− φ2x.

Fur die Startwerte f1 = 1 und f2 = 3 (f0 = 0 ist bedeutungslos) ergibt sich

fn =1√5

(Φ2n − φ2n

)= F2n ,

die 2n–te Fibonacci-Zahl!

Ahnliche Uberlegungen liefern als Anzahl der Spannbaume eines Rades mitn > 2 Speichen L2n − 2, wobei L2n die 2n-te Lucas-Zahl ist.

n 1 2 3 4 5 6 7 8 9

F2n 1 3 8 21 55 144 377 987 2584

L2n − 2 1 5 16 45 121 320 841 2205 5776

Es hat den Anschein, dass bei Rekursionen dieser Art die Koeffizienten der ge-suchten Folgen Linearkombinationen geometrischer Folgen sind. Das werden wirgleich allgemein bestatigen. Zunachst erwahnen wir noch zwei Ausnahmefalle:

Beispiel 4.38 Geometrische Folgen und RekursionDie einzigen geometrischen Folgen fn = an, die die Fibonacci-Rekursion

fn+2 = fn+1 + fn

erfullen, sind außer der Nullfolge nur Φn und (−φ)n. Denn die Rekursion istfur fn= an 6= 0 aquivalent zu a2− a − 1 = 0, d.h. a = Φ oder a = −φ. Diegeometrischen Folgen Φn und (−φ)n bilden also eine Basis des zweidimensio-nalen Losungsraumes der Fibonacci-Rekursion. Geometrische Folgen fn = an

kann man naturlich auch durch eine einfachere Rekursion beschreiben, namlichfn+1 = a fn. Schauen wir uns zwei Varianten an: Die Rekursion

fn+2 = fn+1 + 2fn

123

hat, wie man sofort erkennt, den von den Folgen 2n und (−1)n erzeugtenLosungsraum. Hingegen haben die Losungen der Rekursionsgleichung

fn+2 = 2 fn+1 − fn

die Form fn = an + b, sind also keine Linearkombinationen von geometrischenFolgen! Diese Abweichung resultiert aus der Tatsache, dass der Nenner der er-zeugenden Funktion

f =f0 + (f1 − 2f0)x

1− 2x+ x2

die doppelte Nullstelle 1 hat. Dieses Phanomen wird sich gleich klaren.

Eine (homogene) lineare Rekursion d-ten Grades mit konstanten Koeffizien-ten fur Folgen fn ist von der Form

fn+d = −d∑

m=1

qm fn+d−m , d.h.d∑

m=0

qm fn+d−m = 0

fur ein Polynom q =∑dm=0 qm x

m d-ten Grades mit q0 = 1. Die Fibonacci-Rekursion ist also zum Beispiel eine solche lineare Rekursion zweiten Gradesmit q1 = q2 = −1. Wir nehmen im Folgenden an, dass R ein Korper ist.

Satz 4.39 Fur jedes Polynom

q =d∑

m=0

qm xm =

k∏j=1

(1− λj x)dj ∈ R[x] mit paarweise verschiedenen λj ∈ R

und jede formale Potenzreihe f ∈ R[[x]] sind folgende Aussagen aquivalent:

(1) Rekursion: fn+d = −∑dm=1 qm fn+d−m, d.h.

∑dm=0 qm fn+d−m = 0.

(2) Erzeugende Funktion: Es gibt ein Polynom r vom Grad < d mit f =r

q.

(3) Partialbruchzerlegung: Es gibt Polynome gj ∈ R[x] vom Grad < dj mit

f =k∑j=1

gj(1− λj x)dj

.

(4) Explizite Darstellung: Es gibt Polynome hj vom Grad < dj mit

fn =k∑j=1

hj(n)λjn (n ∈ N0).

Die Folgen, die diese aquivalenten Bedingungen erfullen, bilden einen d-dimensionalen Unterraum von R[[x]] = RN0 .

124

Beweis. Es bezeichne Vj die Menge der Folgen, welche (j) erfullen (j = 1, 2, 3, 4).Man sieht leicht, dass jedes Vj ein Vektorraum der Dimension d ist (zum Beispielkonstruiert man aus (1) rekursiv d Basisvektoren des Losungsraumes; in (2)bilden die Vektoren xm/q mit m < d eine Basis, usw.). Es genugt daher, dieInklusionen (i) V2 ⊆ V1, (ii) V3 ⊆ V2 und (iii) V3 ⊆ V4 zu verifizieren.

(i) Fur f ∈ V2 hat q f = r ∈ R[x] einen Grad kleiner als d, d.h. es gilt

(q f)n+d =∑n+dm=0 qm fn+d−m = 0 fur n ∈ N0, also f ∈ V1.

(ii) Die Summendarstellung eines beliebigen f =∑kj=1

gj

(1−λjx)dj∈ V3 bringt

man auf den Hauptnenner q =∏kj=1(1− λjx)dj und erhalt so ein Polynom

r =∑kj=1 pj

∏i 6=j(1− λi x)di vom Grad <

∑j dj = d mit f = r

q , also f ∈ V2.

(iii) Das Produkt

(−1)dk∏j=1

λjdj = qd

ist nicht Null, also ist jedes der Korperelemente λj invertierbar. Die Ausdrucke

hj(n) =∑i<dj

gji

(n+dj−i−1

dj−1

)λi−i

sind Polynome in n vom Grad < dj und erfullen nach der Binomialformel furgeometrische Reihen die Gleichungen

gj(1− λjx)dj

=∑n

∑i<dj

gji

(n+dj−i−1

dj−1

)λjn−i xn =

∑n

hj(n)λjn xn .

Es folgt f =∑n

fn xn =

k∑j=1

gj(1− λjx)dj

=∑n

hj(n)λjn xn ∈ V4 . �

Eine kurze Zusatzrechnung zeigt:

Bemerkung 4.40 Hat q nur einfache Nullstellen λ1, ..., λk, so ergibt sich diePartialbruchzerlegung

p

q=

k∑j=1

cj1− λjx

durch cj =−λj p( 1

λj)

Dq( 1λj

)

und die explizite Darstellung lautet

fn =k∑j=1

cj λjn .

Im Fibonacci-Beispiel ist q = 1− x− x2, Dq = −1− 2x,

c1 =1

1 + 2φ=

1√5, c2 =

11− 2Φ

= − 1√5.

125

Beispiel 4.41 GeldbetrageAuf wieviele Weisen kann man einen Betrag von n Cent aus 1-, 2- und 5-Cent-Munzen (ohne Beachtung der Reihenfolge) zusammenstellen? Die allgemeineLosung dieser scheinbar harmlosen Aufgabe erweist sich als ziemlich schwierig,doch helfen hier erzeugende Funktionen wirklich weiter: Die gesuchten Zahlenfn sind die Koeffizienten der erzeugenden Funktion

f = (∑n

xn)(∑n

x2n)(∑n

x5n) =1

(1− x)(1− x2)(1− x5).

Die Koeffizienten des Nenners

q = (1− x)(1− x2)(1− x5) = 1− x− x2 + x3 − x5 + x6 + x7 − x8

liefern sofort eine lineare Rekursion achten Grades fur die gesuchten Zahlen:

Mit fn = 0 fur n < 0 und f0 = 1 gilt:

fn = fn−1 + fn−2 − fn−3 + fn−5 − fn−6 − fn−7 + fn−8 (n ∈ N).

Die ersten expliziten Werte samt zugehorigen Summendarstellungen lauten:

f1 = 1 1f2 = 2 2 1 + 1f3 = 2 2 + 1 1 + 1 + 1f4 = 3 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1f5 = 4 5 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1f6 = 5 5 + 1 2 + 2 + 2 2 + 2 + 1 + 1 2 + 1 + 1 + 1 + 1 1 + 1 + ...+ 1f7 = 6 5 + 2 5 + 1 + 1 2 + 2 + 2 + 1 2 + 2 + 1 + 1 + 1 2 + 1 + ...+ 1 1 + ...+ 1

Die vorschnelle Vermutung fn = n− 1 fur alle weiteren n wird zwar noch durchf8 = 7 und f9 = 8 gestutzt, aber bereits durch f10 = 10 widerlegt. Nein, esist leider sehr viel komplizierter! Der Nenner q lasst sich mit Hilfe der funftenEinheitswurzel

ζ = e2πı5

folgendermaßen faktorisieren:

f =1

(1− x)3(1 + x)(1− ζ x)(1− ζ2x)(1− ζ3x)(1− ζ4x),

und die Partialbruchzerlegung muss so aussehen:

f =ax2 + bx+ c

(1− x)3+

d

1 + x+

c11− ζ x

+c2

1− ζ2x+

c31− ζ3x

+c4

1− ζ4x,

wobei man immerhin die Koeffizienten a, d und cj mit der Formel 4.40 mittelsDq = −1− 2x+ 3x2 − 5x4 + 6x5 + 7x6 − 8x7 berechnen kann:

a =110, d =

18, cj =

15

(−1− ζj + ζ2j + ζ4j) (j = 1, 2, 3, 4) .

126

Die Koeffizienten b und c ergeben sich danach durch einen rechnerisch ziemlichmuhseligen Koeffizientenvergleich:

b =14, c =

1340.

Damit lasst sich dann die komplexe Partialbruchzerlegung aufstellen:

f =1

10(1− x)+

14(1− x)2

+13

40(1− x)3+

18(1 + x)

+4∑j=1

cj1

1− ζjx

und daraus eine explizite Darstellung fur die gesuchten Zahlen fn gewinnen:

fn =110

(n+ 2

2

)+

14

(n+ 1) +1340

+18

(−1)n +4∑j=1

cj ζjn .

Mit den komplexen Summanden kann man wenig anfangen – es sollen ja amSchluss naturliche Zahlen als Summanden herauskommen! Die reelle Partial-bruchzerlegung ist hier hilfreicher. Mit rechnerischer Geduld bekommt man

f − 110(1−x)

− 14(1−x)2

− 1340(1−x)3

− 18(1+x)

=1 + x2 − x3 − x4

1− x5

= (1 + x2 − x3 − x4)(1 + x5 + x10 + x15...)

= 1 + x2 − x3 − x4 + x5 + x7 − x8 − x9 + x10 + x12 − x13 − x14... .

Die Koeffizienten dieser Reihe sind

rn = +1 fur n ≡ 0 (5)rn = 0 fur n ≡ 1 (5)rn = +1 fur n ≡ 2 (5)rn = −1 fur n ≡ 3 (5)rn = −1 fur n ≡ 4 (5)

und wir erhalten abschließend

fn =110

(n+ 2

2

)+

14

(n+ 1) +1340

+18

(−1)n +15rn .

Glucklicherweise ist der Rattenschwanz 18 (−1)n+ 1

5 rn betragsmaßig klein genug,um vernachlassigt werden zu konnen.

Ergebnis: fn ist die ganzzahlig gerundete Zahl[110

(n+ 2

2

)+

14

(n+ 1) +1340

]=[

2n2 + 16n+ 2740

].

Soviel zu Theorie und Praxis!

127

Bei der Berechnung der expliziten Darstellung der Folgenglieder fn gemaßSatz 4.39 kann jeder der einzelnen Schritte

Rekursion −→ Nullstellen des Polynoms −→ Partialbruchzerlegung −→ Reihen

im Einzelfall recht aufwendig werden, aber nur der erste, namlich die Nullstel-lenbestimmung, ist im Falle hoherer Grade nicht immer explizit losbar.

Haufig werden bei einer linearen Rekursion die Koeffizienten in umgekehrterReihenfolge indiziert. Man betrachtet dann statt q das sogenannte gespiegelteoder reflektierte Polynom

p := q↔ :=d∑

m=0

qd−m xm =

d∑m=0

qm xd−m = xd q(

1x

) .

Man nennt es auch charakteristisches Polynom der Rekursion

fn+d = q1 fn+d−1 + ...+ qd fn = pd−1 fn+d−1 + ...+ p0 fn .

Die Nullstellen des charakteristischen Polynoms sind genau die λj (mit Viel-fachheit dj) in der Darstellung

q =k∏j=1

(1− λjx)dj , d.h. p =k∏j=1

(x− λj)dj ,

denn es gilt ja p = xd q(1x

) =k∏j=1

xdj (1− λj1x

)dj .

Die Theorie der linearen Rekursionen zeigt augenscheinliche Analogien zulinearen Differentialgleichungen (beide homogen mit konstanten Koeffizienten):

lineare Rekursionsgleichung lineare Differentialgleichung

fn+d + pd−1fn+d−1 + ...+ p0fn = 0 Dng + pd−1Dn−1g + ...+ p1Dg + p0 g = 0

charakteristisches Polynom

p(x) =∑dm=0 pm x

m =∏kj=1(x− λj)dj

Basis des Losungsraumes

ni λjn , i < dj , j ≤ k xi eλjx , i < dj , j ≤ k

allgemeine Losung

fn =∑j≤k

∑i<dj

bij ni λj

n g =∑j≤k

∑i<dj

cij xi eλjx

Besonders deutlich wird der Zusammenhang, wenn man exponentielle erzeugendeFunktionen betrachtet: Ist

g(x) = Ef(x) =∑n

fnn!xn

128

die Taylor-Entwicklung einer Losung g der Differentialgleichung auf der rechtenSeite, d.h. fn = (Dng)(0), so ist f eine Losung der Rekursionsgleichung aufder linken Seite, und umgekehrt. Denn hier bewirkt Differentiation einfach eineIndexverschiebung:

Dm(Ef) =∑n

fn+m

n!xn .

Reihenentwicklung der Exponentialfunktionen eλjx und Koeffizientenvergleichliefert einen direkten Zusammenhang zwischen den Koeffizienten bij und cij :

bij (n)i = cij λji (mit (n)i = n(n− 1)...(n− i+ 1) ).

Beispiele 4.42 Sinus und CosinusMit der Methode der linearen Rekursion kann man die Taylorkoeffizienten vielerwichtiger Reihen der Analysis bestimmen (wie es schon Taylor gemacht hat).

(1) Die Losung von

D2g = g

mit g(0) = 0 und Dg(0) = 1 ist bekanntlich der Sinus Hyperbolicus

sinh(x) =12

(ex − e−x)

mit den Taylorkoeffizienten D2n+1g(0) = 1 und D2n = 0.

Beim Cosinus Hyperbolicus

cosh(x) =12

(ex + e−x) ,

der Losung der selben Differentialgleichung mit den Anfangswerten g(0) = 1und Dg(0) = 0, ist es gerade umgekehrt: D2ng(0) = 1 und D2n+1 = 0.

(2) Basislosungen von

D2g = −g

sind bekanntlich der Sinus und der Cosinus:

sin(x) =∑n

(−1)n

(2n+ 1)!x2n+1 und cos(x) =

∑n

(−1)n

(2n)!x2n.

(3) Die Differentialgleichung

D2g = Dg + g

mit den Anfangswerten g(0) = 0 und (Dg)(0) = 1 fuhrt auf die Losung

g =1√5

(eΦx − e−φx)

mit den Fibonacci-Zahlen Dng(0) = Fn als Taylorkoeffizienten.

129

Wie bei den Differentialgleichungen gibt es bei den Rekursionen sehr vielallgemeinere (und oft erheblich schwierigere bis unlosbare) Situationen:

(A) linear mit variablen Koeffizienten

(B) linear, aber inhomogen (mit einem zusatzlichen Summanden)

(C) nicht linear

Zu jedem dieser Falle wollen wir uns ein paar Beispiele ansehen.

Lineare Rekursionen erster Ordnung haben allgemein die Gestalt

fn+1 = bn fn + cn ,

wobei bn und cn vorgegebene Koeffizientenfolgen sind. Im Falle cn = 0 sindsie homogen. (Manchmal werden scheinbar etwas allgemeinere Rekursionen derForm an fn+1 = bn fn+cn mit an 6= 0 betrachtet, aber diese lassen sich naturlichsofort mittels Division durch an auf die obige Gestalt bringen.)

Per Induktion verifiziert man:

Satz 4.43 Die expliziten Losungen der linearen Rekursion erster Ordnung sind

fn = pn

(f0 +

n∑k=1

ckpk

)mit pk =

k∏j=1

bj .

Beispiel 4.44 Zweielementige TeilmengenNicht homogen, aber mit konstanten Koeffizienten 1 ist die Rekursion

fn+1 = fn + n

fur die Anzahl der zweielementigen Teilmengen einer n-elementigen Menge (esgibt n Moglichkeiten, das (n+1)–te Element zu einem anderen in eine Zweier-menge zu packen). Die Rekursion fuhrt mit f0 = 0 sofort auf die explizite Form

fn =(n+1

2

).

Beispiel 4.45 PermutationenDie Anzahl der Permutationen bzw. linearen Ordnungen einer n-elementigenMenge erfullt die Rekursion

fn = n fn−1 ,

da man das n-te Element auf n Weisen in eine Anordnung der vorherigen n− 1Elemente einfugen kann. Das ist einer der einfachsten Falle einer homogenenlinearen Rekursion mit nichtkonstanten Koeffizienten. Mit f0 = 1 ergibt sichnaturlich sofort die bekannte explizite Gleichung fn = n! , die man auch ausSatz 4.43 mit bn = n, cn = 0 ablesen kann.

130

Die zugehorige erzeugende Funktion hat den Konvergenzradius 0 und ist daherim Sinne der klassischen Analysis unbrauchbar. Hingegen bedeutet die obigeRekursion fn = n fn−1 fur die exponentiell erzeugende Funktion

Ef =∑n

fnn!xn = 1 +

∑n≥1

fn−1

(n− 1)!xn = 1 + xEf ,

also

Ef =1

1− x=∑n

xn (Konvergenzradius 1) .

Damit gelangen wir wieder zu der expliziten Darstellung fn = n!, allerdings miteinem Kanonenschuss auf Spatzen. Jedoch wird schon an diesem sehr einfachenBeispiel das Vorgehen mittels exponentieller formaler Potenzreihen deutlich.

Beispiel 4.46 DerangenmentsIn Satz 1.20 hatten wir die Anzahl Dn der Derangements, d.h. der fixpunktfreienPermutationen von n mittels Inklusion–Exklusion bekommen:

(∗) Dn = n!n∑k=0

(−1)k

k!.

Wir werden dieses Ergebnis jetzt noch auf zwei andere Weisen herleiten.

Durch Summation uber die Anzahlen der Permutationen von n mit n−k Fix-punkten (k = 0, ..., n) erhalten wir folgende Summenformel:

n! =n∑k=0

(n

k

)Dk bzw. 1 =

n∑k=0

Dk

k! (n−k)!.

Sie konnte zwar als lineare Rekursion im erweiterten Sinne angesehen werden,hatte dann aber unbeschrankt wachsenden Grad n. Mit exponentiell erzeugen-den Funktionen geschrieben verwandelt sich diese Gleichung in

ED(x) ex =∑n

n∑k=0

Dk

k!xk

1(n−k)!

xn−k =∑n

xn =1

1− x,

also

ED(x) =e−x

1− x=

(∑n

xn

)(∑k

(−1)k

k!xk

),Dn

n!=

n∑k=0

(−1)k

k!.

Alternativ bekommt man alle fixpunktfreien Permutationen auf n entwederdurch Einfugen des Elements n in einen der Zykel einer fixpunktfreien Permu-tation von n−1 oder durch Zusammenfassen mit einem anderen Element vonn−1 zu einem Zweierzykel und Erganzen durch eine fixpunktfreie Permutationauf der (n−2)–elementigen Restmenge. Das fuhrt auf eine lineare Rekursionzweiten Grades mit nichtkanstanten Koeffizienten:

131

Dn = (n−1)Dn−1 + (n−1)Dn−2.

Im Prinzip kann man wieder die Methode der erzeugenden Funktionen ver-suchen, doch wird das hier wegen des zweiten Grades recht undurchschaubar.Einfacher ist es, diese Rekursion mittels Induktion in eine inhomogene lineareRekursion ersten Grades umzuformen, namlich

Dn = nDn−1 + (−1)n .

Jetzt wendet man Satz 4.43 mit bn = n und cn = (−1)n an und erhalt wiederdie explizite Form (∗).

Beispiel 4.47 PotenzsummenIn Verallgemeinerung von Beispiel 4.44 betrachten wir fur festes m ∈ N0 dieinhomogene lineare Rekursion

σn,m = σn,m−1 + nm

mit Startwert σm,0 = 0 und der Potenzsumme vom Grad m als Losung:

σn,m =n∑k=0

km .

Die Zahl der Summanden wachst dabei unbegrenzt. Vorteilhafter ist die expli-zite Formel, die wir in Beispiel 1.50 mit Hilfe der Stirling-Zahlen zweiter Artgewonnen haben:

σn,m =m∑k=0

Sm,kk+1

(n+1)k+1.

Sie weist σn,m als ein Polynom vom Grad m+1 in n aus, dessen Koeffizientenwir nachher noch auf eine effektivere Weise bestimmen.

Wir halten jetzt n statt m fest und betrachten die exponentiell erzeugendeFunktion fur σn,m:

Eσn(x) =∑m

1m!

σn,m xm =

n∑k=0

∑m

km

m!xm =

n∑k=0

ekx =e(n+1)x − 1ex − 1

.

Die ”doppelt exponentiell erzeugende Funktion” fur σn,m bei variablem m undn ist also∑

n

1n!

∑m

1m!

σn,mxm yn =

∑n

(e(n+1)x − 1)yn

n!(ex − 1)=eexy+x − ey

ex − 1.

132

Beispiel 4.48 Bernoulli-ZahlenDie Bernoulli-Zahlen (benannt nach den Schweizer Mathematikern Johann undJacob Bernoulli) sind rekursiv definiert durch

B0 = 1, Bn = − 1n+1

n−1∑k=0

(n+1k

)Bk bzw.

n∑k=0

(n+1k

)Bk = 0 (n ∈ N) .

Sie treten in vielen zahlentheoretischen, kombinatorischen und analytischen Zu-sammenhangen auf. Die exponentiell erzeugende Funktion

EB(x) =∑n

Bnn!

xn

erfullt aufgrund der Rekursion die Gleichung

EB(x) (ex − 1) =

(∑k

Bkk!

xk

)∑`≥1

x`

`!

=∑n

1n!

(n−1∑k=0

(n

k

)Bk

)xn = x ,

hat also die explizite Form

EB(x) =x

ex − 1.

Damit konnen wir die erzeugende Funktion der Potenzsummen σn,m =∑nk=0 k

m

aus 4.47 (bei festem n) folgendermaßen umschreiben:

Eσn(x) =e(n+1)x − 1

x

x

ex − 1=

(∑k

(n+ 1)k+1

(k + 1)xk

k!

)(∑`

B`x`

`!

),

und durch Auswertung des Cauchy-Produktes bekommen wir

σn,m =m∑k=0

(m

k

)(n+1)k+1

k+1Bm−k =

1m+1

m+1∑`=1

(m+1`

)(n+1)m−`+1B` .

Unter Verwendung der sogenannten Bernoulli-Polynome

Bm(x) =m∑k=0

(m

k

)Bm−k x

k mit Bm(0) = Bm

gelangen wir zu der folgenden einpragsamen Darstellung der Potenzsummen:

σn,m =1

m+1(Bm+1(n+1)−Bm+1) .

Die ersten Werte der Bernoulli-Zahlen sind

B0 = 1 , B1 = − 12, B2 =

16, B3 = 0

und allgemein B2n+1 = 0 fur n ∈ N (warum?), wahrend die spateren Bernoulli-Zahlen B2n betragsmaßig sehr groß werden! Zum Beispiel ist B100 gleich

−9459803781912212529522743306949372187270284153306693613338569620431139541519724771133330 .

133

Die ersten Bernoulli-Polynome lauten

B0(x) = 1 , B1(x) = x− 12, B2(x) = x2 − x+

16, B3(x) = x3 − 3

2x2 +

12x

und fur die Potenzsummen bedeutet das:

σn,0 =11

(n+ 1) = n+ 1 ,

σn,1 =12((n+ 1)2 − (n+ 1)

)=

12

(n+ 1)n ,

σn,2 =13

((n+ 1)3 − 3

2(n+ 1)2 +

12

(n+ 1))

=16

(2n+ 1)(n+ 1)n .

Rechnet man noch ein wenig weiter, gelangt man zu der erstaunlichen, schonArchimedes bekannten Identitat

σn,3 = σ 2n,1 .

Wenden wir uns nun einer nichtlinearen Rekursion fur binare Baume zu, diein der Kombinatorik und Informatik eine wichtige Rolle spielen.

Beispiel 4.49 Vollstandig binare BaumeDarunter versteht man Baume, bei denen genau ein Knoten (die ”Wurzel”) Grad2 und alle anderen Knoten Grad 1 (”Blatter”) oder 3 (”Verzweigungen”) haben.Fur den Induktionsbeginn lasst man auch den Baum mit nur einem Knoten zu.Wir fragen nach der Anzahl bn (nummerierter) vollstandig binarer Baume mitn Knoten. Man sieht schnell, dass bn = 0 fur gerades n sein muss; aber waspassiert bei ungeradem n? Jedenfalls haben solche Baume n+1

2 Blatter und n−32

Verzweigungen.

d1

d@@ ��s s

3!/2 = 3

d@ �c@@ �� ss s

5!/2 = 60d@@ ��c@@ �� cs c@@ ��ss s

7!/8 + 7!/2 = 3150d@@ ��c@@ �� cc@@ �� sss s

d@@ ��c@@ �� c@@ ��c@@ �� c@@ ��c@@ ��s ss s s c@@ ��s s

13!/4 + . . .

Indem man die Wurzeln von je zwei vollstandig binaren Baumen mit einer neuenWurzel verbindet und beachtet, dass auf diese Weise alle neuen Baume zweimalkonstruiert werden, gelangt man zu der folgenden nichtlinearen Rekursion:

bn+1 =n+ 1

2

n∑k=0

(n

k

)bk bn−k (n ∈ N) .

Ubersetzt in die Sprache der exponentiell erzeugenden Funktionen wird darauswegen b0 = 0 und b1 = 1:

134

Eb(x) = x+x

2Eb(x)2 bzw. Eb(x)2 − 2

xEb(x) + 2 = 0

Beachten Sie, dass Eb(x)x wegen b0 = 0 wohldefiniert ist! Die Losung findet man

(im Ring der formalen Potenzreihen!) wie ublich durch quadratische Erganzung:

Eb(x) =1x

(1−√

1− 2x2)

= −∑n≥1

( 12

n

)(−2)n x 2n−1 =

∑n≥1

1n!

n−1∏j=1

(2j−1)x2n−1 .

(Die Losung mit positivem Vorzeichen beim Wurzelanteil fuhrt auf negativeZahlen, die fur bn nicht in Frage kommen). Die gesuchten Koeffizienten sindalso

b2n−1 =(2n− 1)!

n!

n−1∏j=1

(2j − 1) =n−1∏j=1

(2j − 1)(j + n) .

Beispiel 4.50 Catalan-ZahlenDie Losungen der nichtlinearen Rekursion

cn+1 =n∑k=0

ck cn−k

mit c0 = 1 heißen Catalan-Zahlen (nach dem belgischen Mathematiker EugeneCharles Catalan). Wir schreiben die Rekursion wieder in eine Gleichung fur dieerzeugende Funktion um:

c(x) = 1 + x c(x)2 .

Ahnlich wie im vorigen Beispiel ergibt sich die Losung

c(x) =1

2x(1−√

1− 4x)

=12

∑n≥1

( 12

n

)(−4)n xn−1 ,

cn = −12

(−4)n+1

( 12

n+1

)=

1n+1

(2nn

)=(

2nn

)−(

2nn+1

).

Ein direkter Vergleich mit den Zahlen bn aus Beispiel 4.49 liefert

b2n+1 = (2n+1)! 2−n cn .

n 0 1 2 3

cn 1 1 2 5(2n+1)! 2−n 1 3 30 630

b2n+1 1 3 60 3150

135

Catalan-Zahlen treten in Dutzenden von kombinatorischen Problemen auf.Zum Beispiel stimmen sie mit den Anzahlen der folgenden Objekte uberein (wirlisten diese jeweils fur n = 3, cn = 5 auf):

(1) Folgen (a1, ..., an) naturlicher Zahlen mit 1=a1... ≤ ak−1 ≤ ak ≤ k ≤ n(1, 1, 1) (1, 1, 2) (1, 1, 3) (1, 2, 2) (1, 2, 3)

(2) Klammerungen einer Reihe von n+1 Buchstaben

((∗∗)∗)∗ ∗((∗∗)∗) (∗(∗∗))∗ ∗(∗(∗∗)) (∗∗)(∗∗)

(3) Wege eines Turms auf einem Schachbrett mit (n+1)2 Feldern von linksunten nach rechts oben, wobei die Diagonale nie uberschritten werden darf

r r r rrrrr r rr rrrr rr r rrrr r rrr rrr rr rr rr

(4) Ebene Rundwege der Lange 2n + 2 ohne Uberschneidungen, wobeiauf dem ”Hinweg” nur Schritte um 1 nach rechts oder oben, auf dem

”Ruckweg” nur Schritte um 1 nach links oder unten zugelassen sind.

r rrrrrrr r rr rrrrr r r rrrrrr r r rrrrrr r r r rrrrr

(5) Triangulierungen eines konvexen n+ 2-Ecks (d.h. Zerlegungen in Dreieckedurch n− 1 Diagonalen, die sich im Inneren nicht schneiden)

qCC ����q��

q��BBBB qQQqqCC ���q��

q��qQQqqCCq��

q��ZZZ BBBB qQQq qCC �������q�

�

q��qQQqqCCq��

q��ZZZ qQQq

(6) n disjunkte Sehnen, die je zwei von 2n Punkten auf einem Kreis verbinden

&%'$q qq qq q &%'$qTT

q��

q qq q &%'$qTT

qTTqTTTT

qq q &%'$q�� qTTq qq q &%'$q�� q

��

q qq����

q(7) Positionen von n sich nicht schneidenen Kreisen, deren Mittelpunkte auf

einer gemeinsamen Achse liegen

gg g g g���� g g���� g g&%'$ g��

��&%'$

(8) Unnummerierte, ebene, vollstandig binare Baume (bei denen der linke undrechte Ast jeweils nicht vertauscht werden darf) mit 2n+ 1 Knoten

b@@ ��b@@ �� rb@@ �� rr r

b@@ ��b@@ �� rr @@ ��br r

b@@ �� b@@ ��rr@@ ��br rb��@@ b��@@rb��@@r rrb@@ ��b@@ �� br b@@ ��rr r

136

4.4 Großenordnung und Asymptotik

Bei vielen analytischen, zahlentheoretischen oder kombinatorischen Funktionenbzw. Folgen interessiert deren Großenordnung, d.h. die Frage, wie sie sich verhal-ten, wenn das Argument gegen ∞ geht. Insbesondere wird man versuchen, dieGroßenordnung zu bestimmen, wenn man keine explizite Formel fur die zu un-tersuchenden Funktionen hat, wenn sie also implizit bzw. durch eine Rekursionoder eine kombinatorische Beschreibung gegeben sind (wie etwa die Anzahlfolgeder Ordnungen auf n Elementen).

Aber was ist ”die Großenordnung” einer Funktion oder Folge? Diese Fragelasst sich nicht absolut beantworten; jedoch kann man jeweils zwei Funktionenhinsichtlich ihres Wachstums miteinander vergleichen. Das fuhrt zu folgendenexakten Definitionen:

Es seien f und g zwei reelle oder komplexe Funktionen mit unbeschranktemDefinitionsbereich X (z.B. X = N0, Z, Q, R oder C). Man sagt, f wachstlangsamer als g (oder g wachst schneller als f), und schreibt f � g, falls es eineFunktion h mit |f(x)| ≤ |g(x)|h(x) fur alle x ∈ X und limx→∞ h(x) = 0 gibt.Haben die zu betrachtenden Funktionen nur endlich viele Nullstellen, so kanndiese Situation kurz charakterisiert werden durch

f � g ⇐⇒ limx→∞

f(x)g(x)

= 0 .

Offenbar ist � eine strikte Ordnung, d.h. eine irreflexive und transitive (insbe-sondere antisymmetrische) Relation.

Einen schwacheren Vergleich liefert die Abschatzungsrelation � mit

f � g ⇐⇒ ∃ c, d ∈ R ∀x ∈ X (|x| ≥ d =⇒ |f(x)| ≤ c|g(x)|) .

Dies ist offenbar eine Quasiordnung, d.h. eine reflexive und transitive Relation.Ihre Symmetrisierung � ist daher eine Aquivalenzrelation. Man sagt, f und ghaben gleiche Großenordnung und schreibt f � g, falls f � g � f gilt.

Restriktiver ist die folgende Aquivalenzrelation ∼ : Man sagt, f und g sindasymptotisch gleich, in Zeichen

f ∼ g , falls limx→∞

f(x)g(x)

= 1 ,

wobei wieder vorauszusetzen ist, dass g nur endlich viele Nullstellen hat.Die ublichen Schreibweisen f = o(g) statt f � g und f = O(g) statt f � g

werden wir hier nicht benutzen, da sie Gleichungen suggerieren, obwohl weder�noch � eine Aquivalenzrelation ist; korrekt waren die Notationen f ∈ o(g) bzw.f ∈ O(g), wenn man o(g) als Menge der Funktionen f mit f � g und O(g)als Menge der Funktionen f mit f � g interpretiert; aber dies bringt keinewirklichen Vorteile, außer eventuell bei Gleichungen der Form f = g+o(h) oderf + o(h) = g + o(h), die das Gleiche wie f − g � h bedeuten.

Die Aquivalenzrelationen � und ∼ sind mit � und � vertraglich, d.h. ausf � g, h � k und f � h folgt g � k usw.

137

Beispiele 4.51 Großenordnungsvergleiche fur Logarithmen und PotenzenFur feste reelle Zahlen a > 1 und c > 0 gilt:

c � log log x � log x � xc � a|x| � x|x| � c|x|a

.

Hierbei spielt die Basis der Logarithmen keine Rolle, denn es gilt fur beliebigea, b, x > 0 :

loga xlogb x

= loga b , also loga x ∼ loga b logb x � logb x .

Dies zeigt auch, dass log f ∼ log g gelten kann, obwohl nicht einmal f � gerfullt zu sein braucht, etwa bei f(x) = x log x und g(x) = x :

log f(x) = (log x)(1 +log log x

log x) ∼ log x = log g(x) ,

aber

limx→∞

f(x)g(x)

= limx→∞

log x =∞ .

Beispiel 4.52 Unvergleichbarkeit von Funktionen und FolgenDie Quasiordnung � ist nicht total, denn es kann bei zwei Folgen f und gvorkommen, dass weder f � g noch g � f gilt; z.B. erhalten wir fur

fn = n(−1)n und g = n(−1)n+1:

limn→∞

f2n

g2n=∞ , lim

n→∞

g2n+1

f2n+1=∞ .

Bei Polynomen ist der Großenordnungsvergleich sehr einfach:

Lemma 4.53 Zwei Polynome f und g haben genau dann die gleiche Großen-ordnung, wenn sie den gleichen Grad haben; aber sie sind nur dann asymptotischgleich, wenn sie außerdem den gleichen Leitkoeffizienten haben:

f � g ⇐⇒ Grad f < Grad g ,

f � g ⇐⇒ Grad f ≤ Grad g ,

f � g ⇐⇒ Grad f = Grad g ,

f ∼ g ⇐⇒ d = Grad f = Grad g und fd = gd .

Denn es gilt ja (nach ”Kurzen” von xd):

limx→∞

f(x)g(x)

=fd (1 +

∑d−1k=0 fk f

−1d limx→∞ xk−d)

gd (1 +∑d−1k=0 gk g

−1d limx→∞ xk−d)

=fdgd.

Die aus kombinatorischer Sicht wichtigsten großen Zahlen sind die Fa-kultaten. Wir wollen deshalb der Bestimmung ihrer Großenordnung gezielte Auf-merksamkeit widmen. Zunachst gewinnt man durch eine offensichtliche Unter-und Obersummenabschatzung des Integrals uber den naturlichen Logarithmusfolgende Ungleichungen:

138

Lemma 4.54 Fur alle naturlichen Zahlen n gilt:

n log n− n+ 1 < log(n!) < n log n− n+ 2 + log n ,

insbesondere

log(n!) ∼ n log n und e(ne

)n< n! < ne2

(ne

)n.

Beweis. Die ersten beiden Ungleichungen ergeben sich aus

log n− n+ 1 =∫ n

1log x dx <

∑nk=1 log k

<∫ n+1

1log x dx = (n+1) log(n+1)− n < (n+1) log n− n+ 2 ,

wobei die Ungleichung 1 < (n+1) log(n+1) − (n+1) log n < n+1n ≤ 2 eine

Konsequenz des Mittelwertsatzes ist. �

Leider haben wir damit noch nicht die exakte Großenordnung von n! gefunden;der Faktor bei der oberen Schranke ist zu groß. James Stirling entdeckte um1730 die asymptotische Formel fur die Fakultaten, die seinen Namen tragt:

Satz 4.55 n! ∼√

2πn(ne

)n.

Also gilt erst recht

log(n!)− n log n+ n− 12

log n ∼ 12

log(2π) .

Beweis. Da die einzelnen Argumente eher in die Analysis als in die Kombinatorikgehoren, deuten wir sie nur in großen Schritten an.

Man betrachtet die Folgenglieder

an =n! en

nn√

2πn

und findet uber

(n+12

) log(1 +1n

) > (n+12

)(1n− 1

2n2+

13n3− 1

4n4+ ...) ≥ 1

die klassische Abschatzung

anan+1

=1e

(1 +

1n

)n+ 12

> 1 ,

die zeigt, dass an monoton fallt und daher gegen einen Grenzwert g ≥ 0 kon-vergiert. Wir hoffen: g = 1. Definitionsgemaß ist

a2n

an2=

(2n)! e2n n2n 2πn(2n)2n

√4πn (n!)2 e2n

=√nπ

22n

(2nn

).

Wenn wir zeigen konnen, dass dieser Ausdruck fur große n gegen 1 strebt, sindwir fertig, denn dann ist

139

g =limn→∞ a2n

(limn→∞ an)2= limn→∞

a2n

an2= 1 .

Es bleibt also die folgende auf John Wallis (17. Jahrhundert) zuruckgehendeDarstellung von π

2 zu beweisen, die auch von kombinatorischem Interesse ist,weil sie die Großenordnung der mittleren Binomialkoeffizienten liefert:

Satz 4.56n∏j=1

4j2

4j2−1∼ π

2,

(2nn

)∼ 22n

√πn

.

Beweis. Mittels partieller Integration findet man die Rekursion

Cn(x) :=∫ x

0

sin(t)n dt =1

n+1(− cos(x) sin(n)n + nCn−1(x)) (n > 1)

und aus der daraus resultierenden Rekursion cn+1 := Cn+1(π

2) =

n

n+1cn−1:

c2n =π

2

n∏j=1

2j−12j

=π

214n

(2nn

), c2n+1 =

n∏j=1

2j2j+1

=4n

2n+1

(2nn

)−1

.

Im Intervall [ 0, π ] gilt 0 ≤ sin(x) ≤ 1 und sin(x)2n+1 ≤ sin(x)2n ≤ sin(x)2n−1;wegen der Monotonie des Integrals folgt c2n+1 ≤ c2n ≤ c2n−1 bzw.

n∏j=1

4j2

4j2 − 1≤ π

2≤ 2n+ 1

2n

n∏j=1

4j2

4j2 − 1.

Lasst man hier n gegen ∞ gehen, ergibt sich die behauptete Asymptotik fur π2 .

Nun schreibt man das Produkt noch etwas um:n∏j=1

4j2

4j2 − 1=

n∏j=1

(2j)4

(2j−1)2j · 2j(2j+1)=

24n (n!)4

(2n)!2 (2n+1)=

12n+1

(22n(2nn

))2

und erhalt durch anschließendes Wurzelziehen die Asymptotik fur(

2nn

)(denn

2n+1 ist naturlich asymptotisch gleich 2n). �

Das letzte Resultat legt nahe, dass sich der ”Lowenanteil der Binomialkoef-fizienten in der Mitte befindet” (P. Erdos). Tatsachlich macht die Summe allerBinomialkoeffizienten zwischen n

2 −√n und n

2 +√n mehr als 95 % der Gesamt-

summe 2n aus, und zwischen n2 − 2

√n und n

2 + 2√n sind es sogar mehr als

99, 99 % – obwohl die Anzahl der Summanden etwa 4√n, also fur große n ver-

schwindend klein im Vergleich zur Anzahl n+1 aller Summanden ist. Mit Hilfeder Stirlingschen Formel kann man fur jedes feste c ≥ 0 zeigen, dass

(n

bn/2−c√nc)

die Großenordnung 1√n

2n hat.

Bei Rekursionsgleichungen ist eine Großenbestimmung der potentiellenLosungen hilfreich. Im Falle homogener linearer Rekursionen mit konstantenKoeffizienten ist das sofort zu erledigen, wenn man die Nullstellen des charak-teristischen Polynoms kennt:

140

Satz 4.57 Ist λ1 die betragsmaßig großte Nullstelle des charakteristischen Po-lynoms p der Rekursion

fn+d = pd−1 fn+d−1 + ...+ p0 fn

und hat λ1 die Vielfachheit d1, so gibt es Losungen der Großenordnungnd1−1 λn1 , und alle anderen Losungen haben kleinere Großenordnung.

Denn nach Satz 4.39 lautet die allgemeine Losung fn =∑kj=1 hj(n)λjn mit

Polynomen hj vom Grad < dj , und der Term nd1−1 λ1n dominiert die ubrigen

Summanden, wenn h1 den Grad d1 − 1 hat. �

Zum Beispiel gilt fur die Losung der Fibonacci-Rekursion Fn+2 =Fn+1+Fnmit F0 = 0, F1 = 1: Fn ∼ Φn√

5.

Bei Rekursionen mit nichtkonstanten Koeffizienten kann die Bestimmungder Großenordnung der Losungen sehr viel komplizierter werden.

Beispiel 4.58 Großenordnung der PotenzsummenDie Formel

σn,m =n∑k=0

km =m∑k=0

Sm,kk+1

(n+1)k+1

aus 1.50 und 4.47 zeigt ebenso wie die Formel

σn,m =m∑k=0

(m

k

)(n+1)k+1

k+1Bn−k

aus 4.48, dass es sich um Polynome in n vom Grad m + 1 mit Leitkoeffizient1m+1 handelt. So findet man die Asymptotik

n∑k=0

km ∼ nm+1

m+1,

die man auch durch Unter- und Obersummenabschatzung des Integrals∫ n0xm dx erhalten kann.

Bei binaren Suchverfahren (”Ja–Nein-Abfragen”) und ahnlichen Problemenstoßt man oft auf Rekursionen der Form

fn = a fn/b + cn (a ≥ 1 , b > 1) ,

wobei fn/b je nach Problemstellung als fbn/bc oder als fdn/be zu interpretierenist. In dieser Situation kann man den folgenden Satz beweisen:

Satz 4.59 Sei f eine Losung der Rekursion fn = a fn/b + cn (a ≥ 1 , b > 1).

(1) Im Falle cn � nlogb a gilt fn � nlogb a log2 n.

(2) Gibt es ein ε > 0 mit cn � nlogb a+ε und cn/b ≤ ( 1a − ε) cn , so gilt fn � cn.

(3) Gibt es ein ε > 0 mit cn � nlogb a−ε, so gilt fn � nlogb a.

141

Beispiele 4.60 Turniere(1) Die Regeln eines Turniers mogen verlangen, dass in jeder Runde die Halfteder noch im Wettbewerb befindlichen Teilnehmer ausscheidet; bei ungeraderZahl hat ein Teilnehmer ein Freilos. Die Anzahl der Runden, um einen Siegerzu ermitteln, ist dann bei n Teilnehmern gleich blognc. Die Rekursion lautetfn = fn/2 + 1 mit f1 = 0 . Wir haben also a = 1, b = 2, cn = 1 � n0 = nlog2 1,und es ist fn � n0 log2 n im Einklang mit Satz 4.59 (1).

(2) Wandeln wir die Regeln so ab, dass n Runden notig sind, um die Teilneh-merzahl zu halbieren, so verandert sich die Rekursion zu fn = fn/2 + n ; alsoist wieder a = 2, b = 1, aber diesmal cn = n1. Durch Induktion oder iterier-tes Einsetzen finden man die Losung fn = 2n − 2, sofern f1 = 0 und n eineZweierpotenz ist, und allgemein sieht man leicht, dass fn die Großenordnung nhat. Beachten Sie aber, dass Satz 4.59 (2) hier nicht greift, weil kein ε > 0 mitcn/2 ≤ ( 1

2 − ε) cn existiert.

(3) Lautet die Rekursion fn = 2 fn/2 + n, so kommt fur f1 = 1 und Zweier-potenzen n = 2k offenbar fn = n heraus, und allgemein hat fn wieder dieGroßenordnung n. Aber Satz 4.59 (3) ist erst fur fn = a fn + n mit a > 2anwendbar und liefert dann fn ∼ nlog2 a.

Zum Abschluss wollen wir die Anzahlen bestimmter Relationen auf einerMenge mit n Elementen bestimmen, oder zumindest deren Großenordnung.

Relationen auf n Anzahl an log2 an log2 an ∼

beliebig 2n2

n2 n2

reflexiv/irreflexiv 2n2−n n2 − n n2

symmetrisch 2(n2+n)/2 (n2 + n)/2 12n

2

total 3(n2−n)/2 log232 (n2 − n) log23

2 n2

antisymmetrisch 3(n2−n)/22n log232 (n2 − n) + n log23

2 n2

Ordnungen hn =? log2 hn =? 14n

2

totale Ordnungen n!∑nk=1 log2 k n log2 n

Aquivalenzrelationen Sn =∑m Sn,m log2 Sn n log2 n

Die Abschatzung n2/4 ≤ log2 hn ist leicht zu sehen, indem man nur Ord-nungen der Hohe 2 betrachtet. Dass umgekehrt log2 hn � n2/4 gilt, ist erheblichschwerer zu zeigen (Erne, Kleitman und Rothschild 1970).

Erstaunlicherweise ist die Anzahl der zusammenhangenden Ordnungen aufn asymptotisch gleich der Anzahl aller Quasiordnungen auf n (Erne 1970).

142