Mot de Fibonacci

La n-ième lettre du mot de Fibonacci est

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

où φ est le nombre d'or et ${\displaystyle \left\lfloor .\right\rfloor }$ 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 ${\displaystyle S_{n}}$, on obtient le mot ${\displaystyle S_{n+1}}$ en :

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

Que l'on peut aussi écrire :

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

• ${\displaystyle \sigma (1)=0}$ et
• ${\displaystyle \sigma (0)=01}$

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

On dit aussi que le mot infini de Fibonacci est le point fixe du morphisme ${\displaystyle \sigma }$ car ${\displaystyle 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].

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 ${\displaystyle S_{n}}$ vaut le nombre de Fibonacci ${\displaystyle F_{n}}$. On a donc ${\displaystyle |S_{n}|=F_{n}}$ (${\displaystyle |w|}$ dénote la longueur du mot ${\displaystyle w}$) :

	mot	nombre
${\displaystyle n}$	${\displaystyle S_{n}}$	${\displaystyle 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 ${\displaystyle S_{n}}$ :

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

• 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, ${\displaystyle S_{6}}$ privé de ses deux dernières lettres devient ${\displaystyle 010010}$.
• 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 ${\displaystyle 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 ${\displaystyle S_{n+1}=S_{n}S_{n-1}}$ et ${\displaystyle S_{n-1}S_{n}}$ ne diffèrent que par les deux dernières lettres qui sont échangées. Exemple: ${\displaystyle S_{8}=S_{7}S_{6}=(0100101001001)(01001010)}$ et ${\displaystyle S_{6}S_{7}=(01001010)(0100101001001)}$.

• 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 ${\displaystyle u}$, il existe un entier ${\displaystyle N_{u}}$ tel que deux occurrences consécutives de ${\displaystyle u}$ sont à distance au plus ${\displaystyle N_{u}}$. Par exemple, ${\displaystyle N_{0}=1}$ et ${\displaystyle 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 n données par les valeurs successives de la suite Upper Wythoff (suite A001950 de l'OEIS) : ${\displaystyle \lfloor n\varphi ^{2}\rfloor }$. 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) : ${\displaystyle \lfloor n\varphi \rfloor }$. 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 ${\displaystyle 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 à ${\displaystyle 2+\varphi =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.

Encore une analogie entre mots de Fibonacci et nombres de Fibonacci. D'après le théorème de Zeckendorf, tout entier positif ${\displaystyle 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 :

${\displaystyle 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 :

${\displaystyle 010010100100101001010010010100=(010010100100101001010)(01001010)(0)=S_{8}S_{6}S_{2}}$.

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

${\displaystyle {\begin{array}{lcl}2i\mapsto 2i(2i+1)\\2i+1\mapsto 2i+2\end{array}}}$

Ainsi, on a

${\displaystyle {\begin{array}{lcl}0\mapsto 01\quad 1\mapsto 2\\2\mapsto 23\quad 3\mapsto 4\end{array}}}$

etc. Partant de 0, on obtient

${\displaystyle {\begin{array}{lcl}0\\01\\012\\01223\\01223234\end{array}}}$

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 ${\displaystyle (2i)(2i)}$, ${\displaystyle (2i)(2i+1)(2i)}$ et ${\displaystyle (2i+1)(2i)(2i+1)}$ pour ${\displaystyle i>0}$; 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.

• Ensemble syndétique
• Liste de fractales par dimension de Hausdorff
• L-Système

• M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002, 238 p. (ISBN 978-0-521-59924-5, lire en ligne), « Sturmian Words » (autre lien externe)
• (en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences, Cambridge University Press, 2003

• (en) The Golden String of 0s and 1s : une présentation détaillée et accessible, page de Ron Knott sur le site de l'université de Surrey
• Suite de Fibonacci : Biographie - Croissance d'une colonie de lapins - Mots : une introduction, sur le site Jeu et Mathématiques de Jean-Paul Dalavan.
• Karim Zayana et Christophe Lartigue, « Les lapins abeilles de Fibonacci », sur CultureMath, 4 décembre 2021 : un classique revisité.
• (en) [vidéo] The Golden Fibonacci Sequence sur YouTube : le mot infini de Fibonacci sur la spirale d'Ulam