6 Fibonacci-Zahlen und Kombinatorik

Es gibt eine Vielzahl von Fällen, bei denen die Fibonacci-Zahlen bei kombinatorischen Problemen auftauchen. Die folgende Liste erhebt natürlich keinen Anspruch auf Vollständigkeit.

6.1 Als Anzahl der Zerlegungen in 1en und 2en

Auf wieviele verschiedene Arten kann man die Zahl n in IN als Summe von 1en und 2en schreiben, wobei es auf die Reihenfolge der Summation ankommen soll? Also:

1=1 2=1+1 3=1+1+1 4=1+1+1+1
   =2  =1+2  =1+1+2
     =2+1  =1+2+1
       =3+1+1
       =2+2

Man ahnt es schon.

6.1.1 Proposition:

Die Anzahl der Möglichkeiten, die Zahl n auf diese Weise als Summe von 1en und 2en zu schreiben ist genau Fn+1.

Beweis:
Durch Induktion: Jede solche Summe hat entweder die Form 2+(Summe, die n-2 ergibt), oder 1+(Summe, die n-1 ergibt).

Man kann dies auch aus dem Fibonacci-Baum aus Abschnitt 5 ablesen: Und zwar sollen die Fn+1 Möglichkeiten repräsentiert werden durch die Fn+1 Knoten (n+1). Ordnung. Zu jedem dieser Knoten führt genau ein Weg, der, angefangen beim Knoten 2. Ordnung, über genau n Kanten läuft.

Jedesmal, wenn dieser Weg über einen Knoten vom Typ (k) führt, er sich also nicht verzweigen kann, fassen wir die beiden angrenzenden Kanten zu einer einzigen Kante der Länge 2 zusammen. Wir bekommen also eine Sequenz von 1en und 2en, deren Summe genau n ergibt. Es ist klar, daß sich auf diese Weise genau alle Möglichkeiten ergeben.

Als Anzahl der Spiegelungen an zwei Glasplatten

Ein Lichtstrahl fällt auf zwei übereinandergelegte Glasplatten. An jedem Übergang vom optisch dichteren ins optisch dünnere Medium kann er reflektiert werden. Wieviele verschiedene Wege gibt es für den Lichtstrahl, wenn er sich insgesamt genau n-mal spiegelt?

Das Bild stellt die Möglichkeiten für n=3 dar.

...

Für drei Spiegelungen gibt es also genau 5=F5 Möglichkeiten.

6.2.2 Proposition:
Für n Spiegelungen gibt es genau Fn+2 Spiegelungen.
Beweis:

Es gab auch genau Fn+2 Zeckendorf-Sequenzen der Länge <=n (Korollar 4.2.5.). Wir sind also fertig, wenn wir die Spiegelungsmöglichkeiten mit den Zeckendorf-Sequenzen identifizieren können. Und das ist in der Tat kein Problem: Eine Spiegelung an der mittleren Grenzschicht entspricht einer "1", eine Spiegelung an einer der beiden äußeren Grenzschichten einer "0". Die Zeckendorf-Sequenzen zu obiger Abbildung wären also

(1,0,1),   (1,0,0),   (0,0,1),   (0,0,0),   (0,1,0).

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