5 Fibonacci-Bäume

5.1 Der Stammbaum der Kaninchen

Wir reden in diesem Abschnitt natürlich von Bäumen in graphentheoretischem Sinn. Unser "Fibonacci-Baum" soll der Stammbaum der Kaninchen aus der Kaninchenaufgabe von Leonardo von Pisa (s. 1.1) sein. Dieser Baum sieht ungefähr wir folgt aus:

...

Die Zeit läuft in diesem Bild in x-Richtung (1. Jahr bis 6. Jahr). Jeder Knoten des Graphs steht also für ein bestimmtes Kaninchenpaar in einem bestimmten Jahr. Knoten, die zum k. Jahr gehören, nenne ich auch "Knoten k. Ordnung". Es gibt also genau Fk Knoten k. Ordnung.

In obigem Bild entspricht jedes Kaninchenpaar einem horizontalen Zweig des Baums. Die neu produzierten Paare zweigen nach oben ab.

Es gibt zwei Arten von Knoten: Die einen gehören zu den noch nicht geschlechtsreifen Kaninchenpaaren (an diesen enden folglich genau zwei Kanten), die anderen gehören zu den sich bereits fortpflanzenden Paaren (an solchen enden genau drei Kanten). Wir sagen, daß die Knoten vom Typ k ("klein") bzw. g ("groß") sind. Für die Knoten 6. Ordnung habe ich den Typ drangeschrieben. Es gibt genau Fk-1 Knoten vom Typ g der Ordnung k, und genau Fk-2 vom Typ k der Ordnung k.

Die Knoten der Ordnung 5 haben (von unten nach oben) die Typen (gkggk), die der Ordnung 6 also die Typen (gkggkgkg). Man sieht, daß diese Sequenzen aus "g"s und "k"s übereinstimmen, soweit sie definiert sind (bis zur F5 Stelle). Dies gilt lediglich für die Sequenz im 1. Jahr nicht. Dies ist kein Zufall, sondern liegt im wesentlichen daran, daß der Fibonacci-Baum rekursiv definiert ist. Genaueres wird dem Leser als Übung überlassen. Die unendliche Sequenz, die auf diese Weise definiert ist, nenne ich aus Gründen, die später klar werden, "goldene Sequenz".

Außerdem numerieren wir noch die Knoten in jeder Ordnung von unten nach oben, beginnend mit 0 durch. Für die Knoten 6. Ordnung habe ich die Nummern rechts daneben geschrieben. Wir nennen diese Zahl "Level-Nummer".

Der Fibonacci-Baum entsteht rekursiv einfach dadurch, daß man Stücke folgender Form aneinanderkettet:

...

Und zwar werden in jedem Schritt an alle freien *-Enden neue solche Stücke angeklebt, und zwar mit dem +-Ende.

Der Stammbaum eine Drohne

Den obigen Fibonacci-Baum kann man auch als Stammbaum einer männlichen Honigbiene, einer Drohne, auffassen. Und zwar entstehen Drohnen aus unbefruchteten Eiern, sie haben also nur eine Mutter, aber keinen Vater.

Nun stelle man sich vor, der Knoten 1. Ordnung steht für eine Drohne. Seine Mutter ist der Knoten 2. Ordnung. Diese Bienenkönigin hat nun ganz normal Vater und Mutter, die beiden Knoten 3. Ordnung, unten (auf Level 0) die Mutter und oben (auf Level 1 den Vater. Und so geht das dann weiter.

Insbesondere sieht man, daß eine Drohne in der n. Generation Fn-1 Vorfahren hat. Außerdem sieht man, daß die Knoten vom Typ (k) zu den Drohnen gehören, diejenigen vom Typ (g) zu den Bienenköniginnen.

5.2 Die goldene Sequenz

Zunächst einmal braucht man, um die goldene Sequenz niederzuschreiben, nicht zuerst den Baum aufmalen: Die goldene Sequenz der Länge Fn entsteht nämlich, wenn man diejenige der Länge Fn-1 und diejenige der Länge Fn-2 einfach hintereinanderschreibt:

k
g
gk
gkg
gkggk
gkggkgkg
gkggkgkggkggk
gkggkgkggkggkgkggkgkg

Wir wissen schon, daß die Fibonacci-Zahlen etwas mit den Zahlen des goldenen Schnitts $\eta:=(\sqrt{5}-1)/2$ und $\zeta:=(\sqrt{5}+1)/2$ zu tun haben. Wir betrachten nun die Folge $[n\eta]$ für n in IN. Wegen $\vert\eta\vert <1$ ist

a_n:=[(n+1)\eta]-[n\eta]\in\{0,1\}.

Die Folge (an) fängt so an: (1,0,1,1,0,1,0,...). Und dies ist in der Tat die goldene Sequenz:

5.2.1 Proposition:

(an) (n in IN) ist genau die goldene Sequenz, wobei eine "1" einem "g" entspricht, und eine 0 einem "k".

Beweis:
s. [Tognetti].

Für den Beweis braucht man Identitäten wie z.B.

[(k+F_n)\eta]=F_{n-1}+[k\eta]\quad\mbox{ für }0<k<F_{n+1}.

Die Zahlen $[n\eta]$ kann man auch direkt mit Hilfe einer Rekursionsformel ausrechnen:

5.2.2 Proposition:
Definiert man die Folge (G(n)) (n in IN) durch

G(1):=1\quad\mbox{ und }\quad G(n):=n-G(G(n-1)), so gilt: 
G(n)=[(n+1)\eta]=\sum_{k=0}^n a_n.

Beweis:
S. [Tognetti].

5.3 Der Fibonacci-Baum und die Zeckendorf-Darstellung

Der Satz von Zeckendorf (4.1.1.) sagte, daß man jede natürliche Zahl eindeutig als Summe nicht-konsekutiver Fibonacci-Zahlen schreiben kann. Es war auch nicht schwierig, für ein gegebenes n diese Darstellung zu konstruieren.

Im Fibonacci-Baum kann man die Darstellung ebenfalls ablesen. Verfolgt man nämlich einen Zweig in diesem Kaninchenstammbaum, so können ja niemals zwei Knoten vom Typ k aufeinanderfolgen, genau wie in Zeckendorf-Sequenzen niemals zwei 1en aufeinanderfolgen können.

Ist n in IN gegeben, so suche man einen (beliebigen) Knoten mit Level-Nummer n. Man schreibe eine 1, falls der Knoten vom Typ k ist, und eine 0, falls er vom Typ g ist. Nun gehe man im Baum zurück, bis man schließlich ins zweite Jahr (Ordnung 2) kommt, und schreibe für jeden Knoten, an dem man vorbeikommt, auf eben beschriebene Weise eine 1 oder eine 0.

So ergibt sich beispielsweise in obigem Bild für n=6 die Folge

kggkg   bzw.   10010

Dies ist aber genau die zu 6 gehörige Zeckendorf-Sequenz, denn es ist 6=F2+F5.

Warum dies so ist, ist nicht schwer einzusehen und wird abermals dem Leser überlassen.

by Michael Becker, 5/2003. Letzte Änderung: 5/2003.