WikiDer > Fibonacci-Wort

Das Fibonacci-Wörter sind Wörter in einer Reihe aufeinanderfolgender "Wörter" oder "Strings" von a binärAlphabet aus zwei Buchstaben. Wo ein Fibonacci-Zahl ist die Summe der beiden vorhergehenden Zahlen im Fibonaccia-Folge, ist ein Fibonacci-Wort de Verkettung der beiden vorhergehenden Fibonacci-Wörter.

Fibonacci-Wörter sind ein Sonderfall von Sturmsche Worte.

Definition

Angenommen, das Alphabet besteht aus den „Buchstaben“ 0 und 1. so_nein ist der nein-das Fibonacci-Wort. Beginnen Sie mit so₀ = "0" und so₁ = "01". Vor dem nein > 1 ist dann:

so_nein = so_nein−1so_nein−2 (d. h. die Verkettung des vorherigen und des vorherigen Fibonacci-Wortes).

Die aufeinanderfolgenden Fibonacci-Wörter lauten dann:

• ${displaystyle S_{0}}$ =    0
• ${Displaystil S_{1}}$ =    01
• ${displaystyle S_{2}}$ =    010
• ${displaystyle S_{3}}$ =    01001
• ${displaystyle S_{4}}$ =    01001010
• ${displaystyle S_{5}}$ =    0100101001001
• ${displaystyle S_{6}}$ =    010010100100101001010
• ${displaystyle S_{7}}$ =    0100101001001010010100100101001001
• ...

Es Das (unendlich lange) Fibonacci-Wort beginnt also mit: 010010100100101001010010010100100101001010010010100101...^[1].

Substitution oder Morphismus

Von dem nein-das Fibonacci-Wort kann man es nennen nein 1-das Fibonacci-Wort, das durch Anwenden einer Substitution erhalten wird oder Morphismus:

• Ersetze den Buchstaben "1" durch "0"
• Ersetze den Buchstaben "0" durch "01"

Das kann man so schreiben:${displaystyle S_{n 1}=Sigma (S_{n})}$in welchem ${Displaystil-Sigma}$ es Morphismus ist das wie folgt definiert:

• ${Anzeigestil Sigma(1)=0}$ und
• ${displaystyle sigma (0)=01}$

Das unendliche Wort von Fibonacci ist dann ${displaystyle S_{infty}=lim _{nightarrow infty}sigma ^{n}(1)}$.

Grafische Konstruktion

Konstruktion des Fibonacci-Wortes mit einer Geraden mit Steigung ${Anzeigestil Varphi }$ oder ${Anzeigestil Varphi -1}$ (${Anzeigestil Varphi }$ ist der goldene Zahl)

Das Wort von Fibonacci kann auch durch aufeinanderfolgende Schnitte von a gerade Linie mit Steigung ${Anzeigestil Varphi }$ oder ${Anzeigestil Varphi -1}$, mit den horizontalen und vertikalen Linien der gesamten Koordinaten (siehe nebenstehende Abbildung). ${Anzeigestil Varphi }$ ist der goldene Zahl. Die Schnittpunkte mit den horizontalen Linien sind mit "1" und die mit den vertikalen Linien mit "0" gekennzeichnet.

Beziehung zu Fibonacci-Zahlen

Es besteht eine enge Beziehung zwischen den Fibonacci-Zahlen f_nein und die Fibonacci-Wörter so_nein. Die Länge der nein-das Fibonacci-Wort so_nein entspricht dem nein-die Fibonacci-Zahl f_nein. Die Zahl "0" im so_nein entspricht f_nein−1 und die Zahl "1" ist gleich f_nein−2.

Verschiedene Funktionen

• Das nein-der Buchstabe im Fibonacci-Wort ist ${displaystyle 2 leftlfloor {left({n 1}ight),varphi }ightfloor -leftlfloor {left({n 2}ight),varphi }ightfloor }$ in welchem ${Anzeigestil Varphi }$ es goldene Zahl ist und ${displaystyle leftlfloor xightfloor }$ das entier- oder "Boden"-Funktion (nein = 0,1,2...).
• Das unendliche Fibonacci-Wort ist nicht periodisch. Es enthält nirgendwo zwei aufeinanderfolgende "1" oder drei aufeinanderfolgende "0".
• Die letzten beiden Buchstaben der Fibonacci-Wörter sind abwechselnd "01" und "10".
• Das unendliche Fibonacci-Wort enthält nein 1 verschiedene "Teilwörter" der Länge nein. Es gibt drei Unterwörter der Länge 2: "01", "10" und "00"; vier Unterwörter der Länge 3: "001", "010", "100" und "101" usw. Es wird gesagt, dass die Komplexitätsfunktion des unendlichen Fibonacci-Wortes ist gleich nein 1.
• Wenn Sie die letzten beiden Buchstaben eines Fibonacci-Wortes weglassen, behalten Sie a Palindrom Über.
• Das Verhältnis zwischen der Gesamtzahl der Buchstaben und der Zahl der "0" in den Fibonacci-Wörtern so_nein neigt zum Aufsteigen nein zu ${Anzeigestil phi}$, es goldene Zahl.
• Die Zahl 0,01010100... deren Dezimalbruch durch das unendliche Wort von Fibonacci gebildet wird, ist transzendent.

Externer Link

• DR. Ron Knott, "Die Fibonacci-Kaninchenfolge".