Fibonacciwoord

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

Stel dat het alfabet bestaat uit de "letters" 0 en 1. Sn is het n-de Fibonacciwoord. Begin met S0 = "0" en S1 = "01". Voor n > 1 is dan:

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

De opeenvolgende Fibonacciwoorden zijn dan:

  • S_0 =    0
  • S_1 =    01
  • S_2 =    010
  • S_3 =    01001
  • S_4 =    01001010
  • S_5 =    0100101001001
  • S_6 =    010010100100101001010
  • S_7 =    0100101001001010010100100101001001
  • ...

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

Substitutie of morfisme[bewerken]

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: S_{n+1}=\sigma(S_n) waarin \sigma het morfisme is dat als volgt is gedefinieerd:

  • \sigma(1)=0 en
  • \sigma(0)=01

Het oneindige woord van Fibonacci is dan S_{\infty}=\lim_{n\rarr\infty}\sigma^n(1).

Grafische constructie[bewerken]

Opbouw van het Fibonacciwoord met een rechte met helling \varphi of \varphi-1 (\varphi is het gulden getal)

Men kan het woord van Fibonacci ook bekomen door de opeenvolgende snijpunten van een rechte lijn met helling \varphi of \varphi-1, met de horizontale en verticale lijnen van de gehele coördinaten (zie figuur hiernaast). \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[bewerken]

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

Diverse eigenschappen[bewerken]

  • De n-de letter in het Fibonacciwoord is 2+\left\lfloor {\left( {n + 1} \right)\,\varphi} \right\rfloor - \left\lfloor {\left( {n + 2} \right)\,\varphi } \right\rfloor waarin \varphi het gulden getal is en \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 Sn neigt voor stijgende n naar \phi, het gulden getal.
  • Het getal 0,010010100... waarvan de decimale fractie gevormd wordt door het oneindige woord van Fibonacci, is transcendent.

Externe link[bewerken]

Bronnen, noten en/of referenties
  1. rij A003849 in OEIS