Erzeugende Funktionen für bekannte Folgen

Erzeugende Funktionen für bekannte Folgen
Sebastian Seitz-Holzer
13. Juni 2015
1
Geometrische Reihen
Die einfachste Folge ist die konstante Folge 1, 1, 1, .... Die erzeugende Funktion dieser Folge hat
die Form:
G(s) = 1 + s + s2 + s3 + · · ·
Multipliziert man diese Gleichung mit s erhält man
sG(s) = s + s2 + s3 + s4 + · · ·
= G(s) − 1
woraus folgt:
G(s) =
1
1−s
Das Gleiche funktioniert auch für eine beliebige Folge der Form a, ar, ar2 , ar3 , ...:
Ga,r (s) = a + ars + ar2 s2 + ar3 s3 + · · ·
= a(1 + (rs) + (rs)2 + (rs)3 + · · · )
Hieraus folgt wieder:
rsGa,r (s) = Ga,r (s) − a
und
Ga,r (s) =
a
1 − rs
.
Das Ergebnis dieser geometrischen Reihen stimmt überein mit der erzeugenden Funktion (1 −
s)−1 .
2
Die Fibonacci-Folge
Die bekannte Fibonacci-Folge ist durch ihr ersten beiden Terme f0 = f1 = 1 und durch die
Relation
fn+2 = fn+1 + fn
(1)
1
deniert.
Die ersten Zahlen der Fibonacci-Folge sind also:
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Um die erzeugende Funktion zu berechnen
F ib(s) = 1 + s + 2s2 + 3s3 + 5s4 + · · · ,
multipliziert man beide Seiten der Gleichung mit s + s2 :
(s + s2 )F ib(s) = s + s2 + 2s3 + 3s4 + 5s5 + · · ·
+ s2 + s3 + 2s4 + 3s5 + · · ·
= s + 2s2 + 3s3 + 5s4 + 8s5 + · · ·
Also:
(s + s2 )F ib(s) = F ib(s) − 1
Daraus folgt:
F ib(s) =
1
1 − s − s2
Die resultierende Formel kann man als eine Komposition von zwei erzeugenden Funktionen sehen,
nämlich (1 − s)−1 und s + s2 , d.h.
F ib(s) = 1 + (s + s2 ) + (s + s2 )2 + (s + s2 )3 + · · ·
(2)
Die Entwicklung (2) ist ungünstig, da die Summanden der rechten Seite verschieden groÿe Exponenten von s enthalten. Diese machen die expliziten Formeln der Koezienten kompliziert.
Daher ist folgende Formel als Summe von 2 Brüchen besser geeignet:
1
1
−
s − s1
s − s2

1
1
1
− =√  5 s1 1 − s
s2 1 −
s1
1
1
=√
1 − s − s2
5

s
s2

√
√
−1+ 5
2
(3)
und s2 = −1−2 5 sind die Lösungen der quadratischen Gleichung 1 − s − s2 = 0. Der
Schritt (3) liefert folgende Formel:
s1 =
F ib(s) = √
1
5s1
1+
s2
s
+ 2 + ···
s1
s1
−√
1
5s2
s2
s
1+
+ 2 + ···
s2
s2
Folglich:
1
fn = √ (s−1−n
− s2−1−n )
1
5
(−1)n
= √ (sn+1
− sn+1
)
1
2
5

√ !n+1
(−1)n  −1 + 5
= √
−
2
5
2

√ !n+1
−1 − 5

2
Hinweis: Hier hat man s1 s2 = −1 benutzt.
Ein anderer Weg um die erzeugende Funktion der Fibonacci-Zahlen herzuleiten kann man über
die Lineare Algebra machen. Man nehme ein Paar zwei aufeinanderfolgender Fibonacci-Zahlen
fn , fn+1 als Koordinaten eines Vektor im R2 :
fn
fn+1
∈ R2
Dann kann man die Gleichung (1) als Transformation des Vektors
Φ:
fn
7−→
fn+1
fn+1
fn+2
fn
fn+1
fn+1
fn + fn+1
=
zu
fn+1
fn+2
sehen:
(4)
Die Transformation (4) ist linear und kann geschrieben werden in der Form:
Φ:
fn
7−→
fn+1
0
1
1
1
f
2
3
fn+1
n+1
Dies macht man nun analog für den Vektor
zu
fn+2
sich folgende erzeugende Funktion der Fibonacci-Folge:
1
1
1
2
0
1
fn
=Φ
fn+2
fn+3
fn
fn+1
und so weiter. Daraus ergibt
s2 + · · ·
f0
f0
f0
s + Φ2
s2 + Φ3
s3 + · · ·
f1
f1
f1
f0
= (I + Φs + Φ2 s2 + Φ3 s3 + · · · )
f1
f0
= (I − sΦ)−1
.
f1
F (s) =
+
f0
=
+Φ
f1
I ist die Einheitsmatrix I =
3
1
0
s+
.
Rekursive Zusammenhänge und rationale erzeugende Funktionen
Die Fibonacci-Folge ist durch eine rekursive, lineare Gleichung deniert, nämlich fn+2 = fn+1 +
fn . Mit dieser Gleichung konnte man die erzeugende Funktion explizit nden. Dies kann man auf
rationale Funktionen, die auch rekursiv deniert sind, verallgemeinern. Dies gibt das folgende
Theorem an:
3
3.1 Theorem
Sei eine Folge an gegeben durch eine lineare rekursive Denition der Ordnung k mit konstanten
Koezienten c1 , ..., ck ,
(5)
an+k = c1 an+k−1 + c2 an+k−2 + · · · + ck an
und seien a0 , a1 , ..., ak−1 gegeben.
Dann ist die erzeugende Funktion A(s) = a0 + a1 s + a2 s2 + · · · rational und A(s) = Q(s)
P (s) . Q ist
ein Polynom vom Grad k und P hat höchstens den Grad k − 1.
Beweis: Der Beweis wiederholt die Argumentation der Fibonacci-Folge fast Wort für Wort.
Multipliziert man die erzeugende Funktion A(s) mit c1 s + c2 s2 + · · · + ck sk erhält man:
(c1 s + · · · + ck sk )A(s) =
= c1 a0 + c1 a1 s2 + c1 a2 s3 + · · · + c1 ak−1 sk + · · ·
+ c2 a0 s2 + c2 a1 s3 + · · · + c2 ak−2 sk + · · ·
+ c3 a0 s3 + · · · + c3 ak−3 sk + · · ·
···
+ ck a0 sk + · · ·
= P (s) + A(s)
Der Grad des Polynoms P (s) ist höchstens k − 1 und die Koezienten von sn+k stimmen mit
der Gleichung (5) überein. Damit ist das Theorem bewiesen.
Durch das Theorem 2.1 haben wir auch gezeigt, dass das Polynom Q folgende Form hat:
Q(s) = 1 − c1 s − c2 s2 − · · · − ck sk
Wenn man wieder eine vektorwertige erzeugende Funktion betrachtet muss der 2-dimensionale
Vektor bei der Fibonacci-Folge mit einen k-dimensionalen Vektor ersetzt werden:


an
an+1






 ∈ R2

..
.
an+k−1
Die dazugehörige Transformationsmatrix A für die rekursive Gleichung hat die Form:
 
an+1
 an+2  

 
 ..  = 
 .  

an+k

0
0
···
0
ck
0
1
···
···
0
0
0
0
ck−1 ck−2
···
···
0
c2

a0
a1
1
0

0
an
0 
a

n+1

..

.
1 
a
n+k−1
c1
Man erhält folgende erzeugende Funktion


A(s) = (I − sA)−1 

..
.
ak−1
4










Rationale erzeugende Funktionen sind genau die erzeugenden Funktionen der rekursiven Folgen,
was man auch im folgenden Theorem sieht:
3.2 Theorem
P (s)
und
Wenn die erzeugende Funktion A(s) = a0 + a1 s + a2 s2 + · · · rational ist und A(s) = Q(s)
P und Q sind teilerfremd, dann ist für beliebiges n die Folge a0 , a1 , a2 , ... durch folgende lineare
rekursive Gleichung deniert:
an+k = c1 an+k−1 + c2 an+k−2 + · · · + ck an ,
wobei k der Grad von Q ist und c1 , c2 , · · · , ck beliebige Konstanten sind.
Beweis:
4
Rückrichtung des Theorems 2.1.
Das Hadamard-Produkt von erzeugenden Funktionen
4.1 Denition
Das Hadamard-Produkt von zwei erzeugenden Funktionen
A(s) = a0 + a1 s + a2 s2 + · · ·
und
B(s) = b0 + b1 s + b2 s2 + · · ·
ist die erzeugende Funktion
A ◦ B(s) = a0 b0 + a1 b1 s + a2 b2 s2 + · · ·
Also ist das Hadamard-Produkt von zwei Folgen die Folge, deren Elemente die Produkte der
entsprechenden Elemente der einzelnen Folgen sind.
4.2 Theorem
Das Hadamard-Produkt von zwei rationalen erzeugenden Funktionen ist rational.
Um dieses Theorem zu beweisen benötigt man davor noch ein Lemma:
5
4.3 Lemma
Die erzeugende Funktion für eine Folge a0 , a1 , a2 , ... ist rational genau dann, wenn es Zahlen
q1 , ..., ql und Polynome p1 (n), ..., pl (n), sodass für beliebiges n gilt:
(6)
an = p1 (n)q1n + · · · + pl (n)qln
Der Ausdruck auf der rechten Seite von Gleichung (6) wird Quasipolynom der Variable n genannt.
Beweis:
Zunächst notiert man die erzeugende Funktion (1 − qs)−k in folgender Form:
−k
−k 2 2
−k 3 3
qs +
q s −
q s + ···
1
2
3
k
k+1 2 2
k+2 3 3
=1+
qs +
q s +
q s + ···
1
2
3
k
k+1 2 2
k+2 3 3
=1+
qs +
q s +
q s + ···
k−1
k−1
k−1
(1 − qs)−k = 1 −
Der Koezient von sn hat also die Form:
k+n−1 n
(n + 1)(n + 2)...(n + k − 1) n
q = Pk−1 (n)q n
q =
(k − 1)!
k−1
(7)
Pk−1 (n) ist daher ein Polynom in n vom Grad k − 1.
Jede rationale Funktion ist eine Linearkombination von Polynomen und Brüchen der Form
(1 − qi s)−ki , also sind die Koezienten einer rationalen Funktion Quasipolynome.
Man nimmt nun an, dass die Koezienten einer erzeugenden Funktion Quasipolynome sind. Es
bleibt zu zeigen, dass die entsprechende erzeugende Funktion an = p(n)q n rational ist.
Angenommen der Grad des Polynoms p ist k − 1. Dann formen die Polynome P0 , P1 , ..., Pk−1
aus (7) eine Basis im Vektorraum der Polynome vom Grad höchstens k − 1. Allerdings formt
jede Folge von Polynomen vom Grad 0, 1, ..., k − 1 eine Basis in diesem Vektorraum. Also ist p
eine Linearkombination der Polynome Pi und die dazugehörigen erzeugenden Funktion sind eine
Linearkombination der rationalen Funktionen (1 − qs)−j , j = 0, 1, ..., k − 1. Für ein beliebiges
Quasipolynom hat man daher eine Linearkombination von Brüchen mit verschiedenen qi . Damit
ist das Lemma bewiesen.
Das Theorem ist bewiesen durch die Tatsache, dass das Produkt von 2 Quasipolynomen auch ein Quasipolynom ist. Dies folt aus Gleichung (7).
Beweis des Theorems 3.1:
5
Die Catalan-Zahlen
In arithmetischen Ausdrücken ist die Reihenfolge der Rechenschritte bestimmt durch Klammern,
z.B.:
(3 − 1) · (4 + (15 − 9) · (2 + 6))
Entfernt man alle arithmetischen Ausdrücke auÿer die Klammern hat man eine
:
merstruktur
()(()())
6
reguläre Klam-
Hier sind alle regulären Klammerstrukturen mit einem, zwei und drei Klammerpaaren:
()
()()
()()()
()(())
(())
(())()
(()())
((()))
5.1 Denition
Die Catalan − Zahl cn ist die Anzahl von regulären Klammerstrukturen mit n Paaren von
Klammern.
Man setzt c0 = 1. Dann ist die Folge der Catalan-Zahlen wie folgt deniert:
1, 1, 2, 5, 14, 42, 132, ...
Um eine erzeugende Funktion für die Catalan-Zahlen herzuleiten, ndet man erst eine rekursive
Denition für diese Zahlen.
Jede reguläre Klammerstruktur hat folgende zwei Eigenschaften:
(i) Die Anzahl von links- und rechtsoenen Klammern in einer regulären Klammerstruktur müssen gleich sein;
(ii) Die Anzahl von linksoenen Klammern in jedem Anfangssegment einer regulären Klammerstruktur darf nicht weniger als die Anzahl der rechtsoenen Klammern in demselben Segment
sein.
Jede (endliche) Folge von linken und rechten Klammern mit Eigenschaften (i) und (ii) ist eine
reguläre Klammerstruktur.
Alle Klammern in einer regulären Klammerstruktur werden in Paare aufgeteilt: Eine rechte
Klammer gehört zu einer linken Klammer.
Folgende Regel bestimmt die Zugehörigkeit einer rechten Klammer zu einer linken: Das ist die
erste rechte Klammer die rechts neben einer linken Klammer steht, sodass die Klammerstruktur
zwischen diesen beiden eine reguläre Klammerstruktur ist.
Angenommen eine reguläre Klammerstruktur besteht aus n + 1 Klammerpaaren und dem Paar,
das die ganz linke Klammer enthält. Dann formt die Folge von Klammern innerhalb dieses Klammerpaares mit der ganz linken Klammer auch eine reguläre Klammerstruktur.
Die Folge auÿerhalb dieses Paares formt natürlich auch eine reguläre Klammerstruktur: (...)...,
Punkte sollen hier reguläre Klammerstrukturen verdeutlichen.
Falls nun die innere Klammerstruktur aus k Klammerpaaren besteht, dann gibt es n − k Klammerpaare in der äuÿeren Klammerstruktur.
Im Gegenzug kann man für jedes Paar von regulären Klammerstrukturen bestehend aus k und
n − k Klammerpaaren eine neue reguläre Klammerstruktur konstruieren, bestehend aus n + 1
Klammerpaaren, indem man die erste Klammerstruktur einklammert und das Resultat dann mit
der zweiten verbindet.
Diese Prozedur liefert eine rekursive Denition für die Catalan-Zahlen. Dieses Mal ist sie jedoch nicht linear:
cn+1 = c0 cn + c1 cn−1 + · · · + cn c0
7
Zum Beispiel hat man für n = 4:
c5 = c0 c4 + c1 c3 + c2 c2 + c3 c1 + c4 c0
= 1 · 14 + 1 · 5 + 2 · 2 + 5 · 1 + 14 · 1
= 42
Die erzeugende Funktion für die Catalan-Zahlen:
Cat(s) = c0 + c1 s + c2 s2 + · · ·
= 1 + s + 2s2 + 5s3 + · · ·
Quadriert man diese Gleichung und multipliziert das Ergebnis mit s erhält man:
sCat2 (s) = c20 s + (c0 c1 + c1 c0 )s2 + (c0 c2 + c1 c1 + c2 c0 )s3 + · · ·
= s + 2s2 + 5s3 + 14s4 + · · ·
= Cat(s) − 1
woraus sich ergibt:
sCat2 (s) − Cat(s) + 1 = 0
und das führt zu:
√
1 − 4s
(8)
2s
√
(Hier wird '−' vor der Wurzel genommen, da das '+', (1+ 1 − 4s)/2s = 1/s+· · · , eine negativen
Exponenten von s beinhaltet, was mit Cat(s) nicht übereinstimmt.)
Cat(s) =
1−
Die erzeugende Funktion (8) führt zu einer expliziten Formel für die Catalan-Zahlen. Mit der
Newtonschen binomischen Formel,
cn =
1
2
·
1
2
·
3
2
· · · · · 2n−1
· 4n+1
2
,
2(n + 1)!
und multipliziert man den Zähler und Nenner mit n! und teilt mit 2n+1 erhält man:
(2n)!
1
2n
cn =
=
.
n!(n + 1)!
n+1 n
(9)
Die Formel (9) liefert noch eine einfachere rekursive Denition der Catalan-Zahlen:
cn+1 =
4n + 2
cn
n+2
Die Catalan-Zahlen beschreiben noch viel mehr Objekte als nur reguläre Klammerstrukturen.
Zwei Beispiele werden im Folgenden noch kurz erläutert.
8
5.2 Beispiele:
1.) Man hat ein konvexes (n+2)-Eck bei dem die Ecken von 0 bis n + 1 durchnummeriert sind.
Eine diagonale Triangulation ist eine Aufteilung des (n+2)-Ecks in Dreiecke bei denen sich die
Diagonalen jedoch nicht schneiden dürfen.
Sei tn die Anzahl der Triangulationen eines (n+2)-Ecks mit n ≥ 2 und sei t0 = 1. Man macht
eine beliebige Triangulation in diesem (n+2)-Eck. Das erhaltende Dreieck spaltet das (n+2)-Eck
in ein (n-k+3)-Eck und k-Eck auf.
Diesen Prozess kann man, wie bei den regulären Klammerstrukturen, n-mal machen und es ergibt
sich folgende Gleichung:
tn+1 = t0 tn + t1 tn+1 + · · · + tn t0 ,
welche wieder mit der Catalan-Folge übereinstimmt.
2.)Der
Dyck-Weg in der Ebene ist ein weiteres bekanntes Beispiel für die Catalan-Zahlen. Man
bendet sich im 1. Quadranten in der Ebene. Der Dyck-Weg ist eine ununterbrochene Linie,
beginnend im Ursprung, welcher aus den Vektoren (1, 1) und (1, −1) besteht. Der 'Weg' ist zu
Ende wenn man die x-Achse wieder erreicht hat.
Der Zusammenhang mit den Catalan-Zahlen ist klar: Für jeden Vektor (1, 1) 'schreibt' man eine
linke Klammer und für jeden Vektor (1, −1) eine rechte Klammer.
Also ist die Anzahl der Dyck-Wege mit 2n Schritten konsistent mit der n-ten Catalan-Zahl cn .
6
Aufgaben
2.5.
Benutze die erzeugende Funktion der Fibonacci-Zahlen um folgende Identitäten zu zeigen:
1. f0 + f1 + · · · + fn = fn+2 − 1
2. f0 + f2 + · · · + f2n = f2n+1
3. f1 + f3 + · · · + f2n−1 = f2n − 1
4. f02 + f22 + · · · + fn2 = fn fn+1
2.7.
Finde erzeugende Funktion und explizite Formeln für folgende rekursiv denierte Folgen:
1. an+2 = 4an+1 − 4an , a0 = a1 = 1
2. an+3 = −3an + 2 − 3an+1 − an , a0 = 1, a1 = a2 = 0
3. an+3 = 23 an + 2 − 12 an , a0 = 0, a1 = 1, a2 = 2
7
Quellenangabe
1. Sergej K. Lando. Lectures on generating functions. American Mathematical Society, 2003.
9

Download Report