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 $0$ et $1$ et ne contenant pas deux $1$ consécutifs. Le nombre de mots de longueur $n$ dans ce langage est le $n$ -ième nombre de Fibonacci.

Définition

Fixons l'alphabet à $0,1$ . La suite $(S_{n})$ des mots de Fibonacci est définie par $S_{1}=1$ et $S_{2}=0$ , et pour $n>2$ , par :

S_{n}=S_{n-1}S_{n-2}

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

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

$S_{1}=1$
$S_{2}=0$
$S_{3}=01$
$S_{4}=010$
$S_{5}=01001$
$S_{6}=01001010$
$S_{7}=0100101001001$
$S_{8}=010010100100101001010$

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

Expression analytique

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

\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 $\left\lfloor .\right\rfloor$ 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

Les mots de Fibonacci peuvent être définis via un morphisme (ou substitution).

Partant d'un mot de Fibonacci $S_{n}$ , on obtient le mot $S_{n+1}$ en :

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

Que l'on peut aussi écrire :

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

$\sigma (1)=0$ et
$\sigma (0)=01$

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

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

Mots de Fibonacci et nombres de Fibonacci

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

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

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

Diverses propriétés

Propriétés des mots de Fibonacci

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

Propriétés du mot infini de Fibonacci

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 $u$ , il existe un entier $N_{u}$ tel que deux occurrences consécutives de $u$ sont à distance au plus $N_{u}$ . Par exemple, $N_{0}=1$ et $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) : $\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) : $\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 $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 à $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.

Préfixes du mot infini de Fibonacci

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

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 :

010010100100101001010010010100=(010010100100101001010)(01001010)(0)=S_{8}S_{6}S_{2}

.

Extension à des alphabets infinis

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

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

Ainsi, on a

{\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

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

Fractale du mot de Fibonacci

Les trois types de courbes fractales du mot de Fibonacci.

Article détaillé : Fractale 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

(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).

↑ (en) Eric W. Weisstein, « Rabbit Sequence », sur MathWorld.
↑ 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, n^o 2,‎ 1983, p. 131-135 (lire en ligne).
↑ Jean Berstel, « Mots de Fibonacci », Séminaire d’Informatique Théorique, L.I.T.P., Paris,‎ 1980, p. 57-78 (lire en ligne), Observation 1, p. 63.
↑ (en) Michel Rigo et Arnaud Maes, « More on generalized automatic sequences », J. Autom. Lang. Comb., vol. 7, n^o 3,‎ 2002, p. 351-376 (lire en ligne).
↑ ^{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, n^o 2,‎ 2017, P2.52 (lire en ligne, consulté le 14 octobre 2019).
↑ (en) Amy Glen, Jamie Simpson et W.F. Smyth, « More properties of the Fibonacci word on an infinite alphabet », Theoretical Computer Science, vol. 795,‎ 2019, p. 301–311 (ISSN 0304-3975, DOI 10.1016/j.tcs.2019.07.011, arXiv 1710.02782).

Voir aussi

Articles connexes

Bibliographie

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

Liens externes

(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

[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, n^o 2,‎ 1983, p. 131-135 (lire en ligne).

[3] Jean Berstel, « Mots de Fibonacci », Séminaire d’Informatique Théorique, L.I.T.P., Paris,‎ 1980, 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, n^o 3,‎ 2002, p. 351-376 (lire en ligne).

[ZWW-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, n^o 2,‎ 2017, P2.52 (lire en ligne, consulté le 14 octobre 2019).

[GlenSimpson2019-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,‎ 2019, p. 301–311 (ISSN 0304-3975, DOI 10.1016/j.tcs.2019.07.011, arXiv 1710.02782).

[1]

[2]

[3]

[4]

[5]

[6]