Mot de Fibonacci

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

En mathématiques, 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 » réfère aussi parfois aux éléments d'un langage formel composé des mots sur un alphabet de deux lettres et et ne contenant pas deux consécutifs. Le nombre de mots de longueur dans ce langage est le -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 à . La suite des mots de Fibonacci est définie par et , et pour , par :

(le produit est la concaténation des deux précédents termes).

Le mot infini de Fibonacci, noté , est la limite de cette suite, c'est-à-dire l'unique mot infini dont tous les mots 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 :

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

φ est le nombre d'or et 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 , on obtient le mot en :

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

Que l'on peut aussi écrire :

avec le morphisme défini par :

  • et

et, pour le mot infini de Fibonacci, .

On dit aussi que le mot infini de Fibonacci est le point fixe du morphisme car . 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 vaut le nombre de Fibonacci . On a donc ( dénote la longueur du mot ) :

mot nombre de 1
 
1 1 1
2 10 1
3 101 2
4 10110 3
5 10110101 5
6 1011010110110 8
7 101101011011010110101 13
8 1011010110110101101011011010110110 21

De même, on montre que, dans  :

  • le nombre de "0" vaut
  • le nombre de "1" vaut

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, privé de ses deux dernières lettres devient
  • En préfixant un mot de Fibonacci par le complément binaire de ses deux dernières lettres, on obtient un palindrome. Ainsi 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 et ne diffèrent que par les deux dernières lettres qui sont échangées. Exemple: et .

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 , il existe un entier tel que deux occurrences consécutives de sont à distance au plus . Par exemple, et . 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) : .
  • Les lettres "0" se situent aux positions données par les valeurs successives de la suite Lower Wythoff (suite A000201 de l'OEIS) : .
  • Le mot de Fibonacci admet des répétitions de 3 facteurs identiques (cubes); ainsi "(010(010)(010)" est facteur de , 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 à , 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 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 :

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 :

.

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]