En mathématiques et plus précisément en combinatoire des mots, 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 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

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

Expression analytique

modifier

La n-iè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, tandis que la suite du Lapin est de pente φ – 1 (voir figure plus haut).

Règle de substitution ou morphisme

modifier

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,  .

Le mot de Fibonacci est donc un mot substitutif. 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

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
      
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   :

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

Diverses propriétés

modifier

Propriétés des mots de Fibonacci

modifier
  • 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 (conséquence évidente de la propriété précédente). 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
  • 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 n données par les valeurs successives de la suite Upper Wythoff (suite A001950 de l'OEIS) :  . Les n en question sont aussi les entiers pour lesquels la décomposition en somme de nombres de Fibonacci par ordre décroissant se termine par un nombre de Fibonacci dont l'indice est impair.
  • Les lettres "0" se situent aux positions données par les valeurs successives de la suite Lower Wythoff (suite A000201 de l'OEIS) :  . Les n en question sont aussi les entiers pour lesquels la décomposition en somme de nombres de Fibonacci par ordre décroissant se termine par un nombre de Fibonacci dont l'indice est pair.
  • Le bit n du mot de Fibonacci est le bit de poids faible de la représentation de Zeckendorf de n[3],[4].
  • 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

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 :

 .

Extension à des alphabets infinis

modifier

La suite de Fibonacci a été étendue à un alphabet infini[5]. On prend pour alphabet l'ensemble   des entiers et on définit un morphisme par :

 

Ainsi, on a

 

etc. Partant de 0, on obtient

 

Le mot infini obtenu, en passant à la limite est :

0 1 2 2 3 2 3 4 2 3 4 4 5 2 3 4 4 5 4 5 6 ...

Modulo 2, on retrouve la suite de Fibonacci usuelle

0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 ...

De nombreuses propriétés combinatoire de la suite de Fibonacci s'étendent à cette généralisation. Les auteurs de l'article de 2017 en ont décrit quelques-unes[5]. Ainsi, ils montrent que les palindromes de la suite généralisée sont de longueur 2 ou 3, et que ce sont les mots  ,   et   pour  ; d'autres ont été données par Amy Glen,Jamie Simpson et W.F. Smyth[6]. Les auteurs étudient les occurrences de carrés, de palindromes et de mots de Lyndon dans ce mot infini.

Fractale du mot de Fibonacci

modifier
 
Les trois types de courbes fractales du mot de Fibonacci.

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

Notes et références

modifier
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fibonacci word » (voir la liste des auteurs).
  1. (en) Eric W. Weisstein, « Rabbit Sequence », sur MathWorld.
  2. Ce résultat est démontré par Jean-Jacques Pansiot, « Mot infini de Fibonacci et morphismes itérés », RAIRO-Informatique théorique, vol. 17, no 2,‎ , p. 131-135 (lire en ligne).
  3. Jean Berstel, « Mots de Fibonacci », Séminaire d’Informatique Théorique, L.I.T.P., Paris,‎ , p. 57-78 (lire en ligne), Observation 1, p. 63.
  4. (en) Michel Rigo et Arnaud Maes, « More on generalized automatic sequences », J. Autom. Lang. Comb., vol. 7, no 3,‎ , p. 351-376 (lire en ligne).
  5. a et b (en) Jiemeng Zhang, Zhixiong Wen et Wen Wu, « Some properties of the Fibonacci sequence on an infinite alphabet », Electronic Journal of Combinatorics, vol. 24, no 2,‎ , P2.52 (lire en ligne, consulté le ).
  6. (en) Amy Glen, Jamie Simpson et W.F. Smyth, « More properties of the Fibonacci word on an infinite alphabet », Theoretical Computer Science, vol. 795,‎ , p. 301–311 (ISSN 0304-3975, DOI 10.1016/j.tcs.2019.07.011, arXiv 1710.02782).

Voir aussi

modifier

Articles connexes

modifier

Bibliographie

modifier

Liens externes

modifier