Fibonacciwoord

De Fibonacciwoorden zijn woorden in een rij van opeenvolgende "woorden" of "strings" uit een binair alfabet van twee letters. Waar een Fibonaccigetal de som is van de twee voorgaande getallen in de rij van Fibonacci, is een Fibonacciwoord de concatenatie van de twee voorgaande Fibonacciwoorden.

Fibonacciwoorden zijn een bijzonder geval van Sturmiaanse woorden.

Definitie

Stel dat het alfabet bestaat uit de "letters" 0 en 1. S_n is het n-de Fibonacciwoord. Begin met S₀ = "0" en S₁ = "01". Voor n > 1 is dan:

S_n = S_n−1S_n−2 (dus de concatenatie van het vorige en het voor-vorige Fibonacciwoord).

De opeenvolgende Fibonacciwoorden zijn dan:

• ${\displaystyle S_{0}}$ =    0
• ${\displaystyle 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
• ...

Het (oneindig lange) Fibonacciwoord begint dus met: 010010100100101001010010010100100101001010010010100101....

Substitutie of morfisme

Uit het n-de Fibonacciwoord kan men het n+1-de Fibonacciwoord bekomen door toepassing van een substitutie of morfisme:

• vervang de letter "1" door "0"
• vervang de letter "0" door "01"

Men kan dit schrijven als: ${\displaystyle S_{n+1}=\sigma (S_{n})}$ waarin ${\displaystyle \sigma }$ het morfisme is dat als volgt is gedefinieerd:

• ${\displaystyle \sigma (1)=0}$ en
• ${\displaystyle \sigma (0)=01}$

Het oneindige woord van Fibonacci is dan ${\displaystyle S_{\infty }=\lim _{n\rightarrow \infty }\sigma ^{n}(1)}$.

Grafische constructie

Men kan het woord van Fibonacci ook bekomen door de opeenvolgende snijpunten van een rechte lijn met helling ${\displaystyle \varphi }$ of ${\displaystyle \varphi -1}$, met de horizontale en verticale lijnen van de gehele coördinaten (zie figuur hiernaast). ${\displaystyle \varphi }$ is het gulden getal. De snijpunten met de horizontale lijnen duidt men aan met "1" en die met de verticale lijnen met "0".

Verband met Fibonaccigetallen

Er bestaat een nauw verband tussen de Fibonaccigetallen F_n en de Fibonacciwoorden S_n. De lengte van het n-de Fibonacciwoord S_n is gelijk aan het n-de Fibonaccigetal F_n. Het aantal "0" in het S_n is gelijk aan F_n−1 en het aantal "1" is gelijk aan F_n−2.

Diverse eigenschappen

• De n-de letter in het Fibonacciwoord is ${\displaystyle 2+\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor -\left\lfloor {\left({n+2}\right)\,\varphi }\right\rfloor }$ waarin ${\displaystyle \varphi }$ het gulden getal is en ${\displaystyle \left\lfloor x\right\rfloor }$ de entier- of "floor"functie (n = 0,1,2...).
• Het oneindige Fibonacciwoord is niet periodiek. Het bevat nergens twee opeenvolgende "1" of drie opeenvolgende "0".
• De twee laatste letters van de Fibonacciwoorden zijn afwisselend "01" en "10".
• Het oneindige Fibonacciwoord bevat n+1 verschillende "subwoorden" van lengte n. Er zijn drie subwoorden van lengte 2: "01", "10" en "00"; vier subwoorden van lengte 3: "001", "010", "100" en "101" enz. Men zegt dat de complexiteitsfunctie van het oneindige Fibonacciwoord gelijk is aan n+1.
• Als men de twee laatste letters van een Fibonacciwoord weglaat houdt men een palindroom over.
• De verhouding tussen het totaal aantal letters en het aantal "0" in de Fibonacciwoorden S_n neigt voor stijgende n naar ${\displaystyle \phi }$, het gulden getal.
• Het getal 0,010010100... waarvan de decimale fractie gevormd wordt door het oneindige woord van Fibonacci, is transcendent.

Externe link

• Dr. Ron Knott, "The Fibonacci Rabbit sequence".