Mot de Fibonacci

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un mot de Fibonacci est une suite particulière de symboles pris dans un alphabet quelconque de deux lettres. Les mots de Fibonacci sont à l'opération de concaténation ce que les nombres de Fibonacci sont à l'addition. Le mot de Fibonacci infini est l'exemple paradigmatique de mot sturmien.

Le nom « mot de Fibonacci » refère aussi parfois aux éléments d'un langage formel composé des mots sur un alphabet de deux lettres 0 et 1 et ne contenant pas deux 1 consécutifs. Le nombre de mots de longueur n dans ce langage est le n-ième nombre de Fibonacci.

Caractérisation du mot infini de Fibonacci par une droite de pente φ-1, où φ est le nombre d'or

Définition[modifier | modifier le code]

Fixons l'alphabet à 0,1. La suite (S_n) des mots de Fibonacci est définie par S_1=1 et S_2=0, et pour n>2, par :

S_n = S_{n-1}S_{n-2} (le produit est la concaténation des deux précédents termes).

Le mot infini de Fibonacci, noté S_{\infty}, est la limite de cette suite, c'est-à-dire l'unique mot infini dont tous les mots S_n sont des préfixes. Les mots de Fibonacci sont appelés ainsi par analogie avec les nombres de Fibonacci, puisque le procédé de construction est analogue, en remplaçant l'addition par la concaténation.

Les premiers mots de Fibonacci sont :

  • S_1=1
  • S_2=0
  • S_3=01
  • S_4=010
  • S_5=01001
  • S_6=01001010
  • S_7=0100101001001
  • S_8=010010100100101001010

Le mot infini de Fibonacci commence donc par :

0100101001001010010100100101001001…

Ce mot infini est la suite A003849 de l'OEIS. On trouve dans la littérature également le terme Rabbit sequence[1] (c'est-à-dire « suite de lapins », en référence au problème de la croissance du nombre de lapins, de génération en génération).

Propriétés[modifier | modifier le code]

Expression analytique[modifier | modifier le code]

La nième lettre du mot de Fibonacci est

\left\lfloor {(n+2)(2-\varphi)} \right\rfloor  - \left\lfloor {(n+1)(2-\varphi)} \right\rfloor
=2+\left\lfloor {\left( {n + 1} \right)\,\varphi} \right\rfloor - \left\lfloor {\left( {n + 2} \right)\,\varphi } \right\rfloor

φ est le nombre d'or et \left\lfloor . \right\rfloor est la fonction partie entière.

Le mot infini de Fibonacci est donc le mot sturmien de pente 2-φ=1/φ2, où φ est le nombre d'or, tandis que la suite du Lapin est de pente φ-1 (voir figure plus haut).

Règle de substitution ou morphisme[modifier | modifier le code]

Les mots de Fibonacci peuvent être définis via un morphisme (ou substitution).

Partant d'un mot de Fibonacci S_n, on obtient le mot S_{n+1} en :

  • remplaçant la lettre "1" par "0"
  • remplaçant la lettre "0" par "01"

Que l'on peut aussi écrire :

S_{n+1}=\sigma(S_n) avec \sigma le morphisme défini par :

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

et, pour le mot infini de Fibonacci, S_{\infty}=\lim_{n\to\infty}\sigma^n(1).

On dit aussi que le mot infini de Fibonacci est le point fixe du morphisme \sigma car S_{\infty}=\sigma(S_{\infty}). Ce morphisme est appelé « morphisme de Fibonacci ». L'ensemble des morphismes pour lesquels le mot infini de Fibonacci est un point fixe est un monoïde, pour la composition. Ce monoïde est engendré par le seul morphisme de Fibonacci[2].

Mots de Fibonacci et nombres de Fibonacci[modifier | modifier le code]

Les mots de Fibonacci et les nombres Fibonacci sont étroitement liés. Chaque mot de Fibonacci étant la concaténation des deux précédents et partant de "1", puis "0", alors la longueur du mot de Fibonacci S_n vaut le nombre de Fibonacci F_n. On a donc |S_n| = F_n (|w| dénote la longueur du mot w) :

mot longueur
n  S_n F_n
1 1 1
2 0 1
3 01 2
4 010 3
5 01001 5
6 01001010 8
7 0100101001001 13
8 010010100100101001010 21

De même, on montre que, dans S_n :

  • le nombre de "0" vaut F_{n-1}
  • le nombre de "1" vaut F_{n-2}

Diverses propriétés[modifier | modifier le code]

Propriétés des mots de Fibonacci[modifier | modifier le code]

  • Les deux dernières lettres d'un mot de Fibonacci sont alternativement "01" et "10"
  • En supprimant les deux dernières lettres d'un mot de Fibonacci, on obtient un palindrome. Ainsi, S_6 privé de ses deux dernières lettres devient 010010
  • En préfixant un mot de Fibonacci par le complément binaire de ses deux dernières lettres, on obtient un palindrome. Ainsi 01S_6=0101001010 est un palindrome.
  • Un mot de Fibonacci ne contient jamais le facteur "11" ni "000".
  • La concaténation de deux mots de Fibonacci successifs est "presque commutative". Plus précisément, les mots S_{n+1}=S_nS_{n-1} et S_{n-1}S_n ne diffèrent que par les deux dernières lettres qui sont échangées. Exemple: S_8=S_7S_6=(0100101001001)(01001010) et S_6S_7 = (01001010)(0100101001001).

Propriétés du mot infini de Fibonacci[modifier | modifier le code]

  • Le mot infini de Fibonacci n'est pas périodique. Il n'est pas, non plus, ultimement périodique.
  • Dans le mot infini de Fibonacci, le rapport (nombre de lettres/nombre de "0") tend vers φ, le nombre d'or ; de même pour le rapport (nombre de "0"/nombre de "1").
  • Dans le mot infini de Fibonacci, le nombre de facteurs distincts de longueur k est k+1. Le mot infini de Fibonacci est donc un mot sturmien. Ainsi, les facteurs distincts de longueur 3 sont au nombre de quatre : "001", "010", "100" et "101". Un tel mot, s'il est apériodique, est dit de « complexité minimale ».
  • Comme tout mot sturmien, le mot de Fibonacci est « équilibré » : soient deux facteurs de même longueur pris n’importe où dans le mot de Fibonacci, la différence entre le nombre de "0" de l’un et le nombre de "0" de l’autre ne dépasse jamais la valeur 1.
  • Chaque facteur du mot infini de Fibonacci y apparaît une infinité de fois. De plus, deux occurrences consécutives d'un même facteur ne sont jamais très espacées: plus précisément, pour tout facteur u, il existe un entier N_u tel que deux occurrences consécutives de u sont à distance au plus N_u. Par exemple, N_0=1 et N_1=2. Un mot qui a cette propriété est appelé « uniformément récurrent ».
  • Si un mot est facteur du mot infini de Fibonacci, alors son image miroir (ou retourné) l'est aussi.
  • Le nombre 0,010010100…, dont les décimales sont construites à partir du mot infini de Fibonacci, est transcendant.
  • Les lettres "1" se situent aux positions données par les valeurs successives de la suite Upper Wythoff (suite A001950 de l'OEIS) : \lfloor n\varphi^2\rfloor.
  • Les lettres "0" se situent aux positions données par les valeurs successives de la suite Lower Wythoff (suite A000201 de l'OEIS) : \lfloor n\varphi\rfloor.
  • Le mot de Fibonacci admet des répétitions de 3 facteurs identiques (cubes); ainsi "(010(010)(010)" est facteur de S_8, mais pas de répétitions de puissance 4. On montre que le mot de Fibonacci admet des répétitions d'exposant inférieurs à 2+\phi=3,618, mais pas d'exposant plus élevés C'est le plus faible index (ou « exposant critique ») parmi les mots sturmiens.
  • Les palindromes qui apparaissent dans le mot infini de Fibonacci sont le mot vide et 0, 1, 00,010,101,1001,01010, 00100,... Plus généralement, il y a exactement 1 palindrome de longueur paire, et deux palindromes de longueur impaire, pour toute longueur. Cette propriété est caractéristique des mots sturmiens.
  • En analyse de la complexité des algorithmes, le mot de Fibonacci est souvent cité comme le « pire cas » pour un algorithme de recherche de répétitions dans une chaine de caractères.

Préfixes du mot infini de Fibonacci[modifier | modifier le code]

Encore une analogie entre mots de Fibonacci et nombres de Fibonacci. D'après le théorème de Zeckendorf, tout entier positif N est somme de nombres de Fibonacci distincts, et cette décomposition est unique si elle n'utilise pas deux nombres de Fibonacci consécutifs. Par exemple :

30=21+8+1=F_8+F_6+F_2

De même, tout préfixe non vide du mot infini de Fibonacci est le produit de concaténation de mots de Fibonacci finis, les mots correspondants étant ceux associé à la décomposition de sa longueur. Ainsi, le préfixe de longueur 30 du mot infini se factorise comme suit :

010010100100101001010010010100= (010010100100101001010)(01001010)(0)=S_8S_6S_2.

Fractale du mot de Fibonacci[modifier | modifier le code]

Les trois types de courbes fractales du mot de Fibonacci.

Sur les autres projets Wikimedia :

Article détaillé : Fractale du mot de Fibonacci.

La fractale du mot de Fibonacci[3] se construit itérativement en appliquant au mot de Fibonacci la règle OEDR (Odd-Even Drawing Rule).

Notes et références[modifier | modifier le code]

  1. (en) Eric W. Weisstein, « Rabbit Sequence », MathWorld
  2. Ce résultat est démontré par Pansiot (1983).
  3. (en) A. Monnerot-Dumaine, The Fibonacci Word fractal, sur HAL

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences, Cambridge University Press, 2003

Liens externes[modifier | modifier le code]