Mot de Fibonacci

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. 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 . On trouve dans la littérature également le terme Rabbit sequence (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). La n-ième lettre du mot de Fibonacci est où φ 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/φ, tandis que la suite du Lapin est de pente φ – 1 (voir figure plus haut). 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 .