Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Mot de Fibonacci
Résumé
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 .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.