Mot de Fibonacci

Un mot de Fibonacci est une suite spécifique de lettres ou 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.

Caractérisation par une droite de pente φ-1, où φ est le nombre d'or

Définition

À partir de l'alphabet {0;1}, Posons $S 1$ = "1" et $S 2$ = "0". alors le mot de Fibonacci $S n = S n - 1 S n - 2$ (la concaténation des deux précédents termes).

Le mot infini de Fibonacci est la limite $S_{\infty}$ .

Le mot de Fibonacci est baptisé par analogie avec la suite de Fibonacci, en substituant l'addition par la concaténation.

Les mots de Fibonacci successifs 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 : 010010100100101001010… Cette suite infinie est la suite A003849 de l’OEIS.

On trouve dans la littérature également les termes Rabbit sequence^[1] et « suite du Lapin »^{[réf. nécessaire]}, qui désignent le mot identique au mot de Fibonacci en inversant "0" et "1". La suite du Lapin commence donc par 101101011…

Propriétés

Expression analytique

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

$\left\lfloor {(n+2)(2-\varphi)} \right\rfloor - \left\lfloor {(n+1)(2-\varphi)} \right\rfloor =2+\left\lfloor {\left( {n + 1} \right)\,\varphi} \right\rfloor - \left\lfloor {\left( {n + 2} \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/φ², où φ est le nombre d'or, 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 = σ(S n)$ avec $σ$ le morphisme défini par :

$σ(1) = 0$ et
$σ(0) = 01$

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

On dit aussi que le mot infini de Fibonacci est le point fixe du morphisme $σ$ car $S_{\infty}=\sigma(S_{\infty})$ . Ce morphisme est appelé « morphisme de Fibonacci ».

Mot de Fibonacci et suite de Fibonacci

Mot de Fibonacci et suite de 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 écrit: $| S n | = F n$

$S n$	long.= $F n$
1	1
0	1
01	2
010	3
01001	5
01001010	8
0100101001001	13
010010100100101001010	21

De même, on montre que :

le nombre de "0" vaut $F n - 1$
le nombre de "1" vaut $F n - 2$

Diverses propriétés

Le mot infini de Fibonacci n'est pas périodique. Il n'est pas, non plus, ultimement périodique.
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.
En juxtaposant le complément binaire des deux dernières lettres d'un mot de Fibonacci au début de ce mot, on obtient un palindrome. Ainsi 01 $S 6$ = 0101001010 est un palindrome.
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").
On ne peut trouver dans un mot de Fibonacci le facteur (ou « sous-mot ») "11" ni "000".
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". Étant non périodique, ce mot est alors de 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 apparait une infinité de fois.
Si un mot est facteur du mot infini de Fibonacci, alors son inverse l'est aussi.
La concaténation de deux mots de Fibonacci successifs est "presque commutative". Ainsi, $S n + 1 = S n S n - 1$ et $S n - 1 S n$ diffèrent seulement sur les deux dernières lettres. Exemple: $S 8 = S 7 S 6 = (0100101001001)(01001010)$ et $S 6 S 7 = (01001010)(0100101001001)$ .
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 données par les valeurs successives de la suite Upper Wythoff (suite A001950 de l’OEIS) : $\lfloor n\varphi^2\rfloor$
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$
Le mot de Fibonacci admet des répétitions de 3 sous-mots (cubes), comme "010", mais pas de répétitions de 4 sous-mots. On montre que le mot de Fibonacci admet au plus $2 + ϕ = 3,618$ répétitions. C'est le plus faible index (ou « exposant critique ») parmi les mots sturmiens.
En théorie de la complexité, 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.

Fractale du mot de Fibonacci

Les trois types de courbes fractales du mot de Fibonacci.

Sur les autres projets Wikimedia :

« la fractale du mot de Fibonacci », sur Wikimedia Commons (ressources multimédia)

Article détaillé : Fractale du mot de Fibonacci.

La fractale du mot de Fibonacci^[2] 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 », MathWorld
↑ (en) A. Monnerot-Dumaine, The Fibonacci Word fractal, sur HAL

Voir aussi

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
J.-J. Pansiot, « Mot infini de Fibonacci et morphismes itérés », dans RAIRO-Informatique théorique, vol. 17, n^o 2, 1983, p. 131-135
(en) The Golden Fibonacci Sequence sur YouTube [vidéo] : le mot infini de Fibonacci sur la spirale d'Ulam

Bibliographie

M. LothaireM. Lothaire, Algebraic Combinatorics on Words, Cambridge UK, Cambridge University Press, 2002 (ISBN 978-0-521-59924-5) [lire en ligne], « Sturmian Words »
(en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences, Cambridge University Press, 2003

Portail des mathématiques

Catégorie :

Suite d'entiers

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Mot de Fibonacci de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

Fractale du mot de Fibonacci — Les trois types de courbes fractales du mot de Fibonacci. La fractale du mot de Fibonacci est une courbe fractale définie dans le plan à partir du mot de Fibonacci. Sommaire 1 … Wikipédia en Français
Fibonacci number — Suite de Fibonacci La suite de Fibonacci est une suite d entiers très connue. Elle doit son nom à un mathématicien italien connu sous le nom de Leonardo Fibonacci qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci,… … Wikipédia en Français
Mot sturmien — En mathématiques, un mot sturmien est un type de mot infini. Sommaire 1 Définition 1 2 Définition 2 3 Mot standard ou mot caractéristique 4 Histoire … Wikipédia en Français
Fibonacci — Leonardo Fibonacci Leonardo Pisano Leonardo Fibonacci (v. 1175 à Pise, Italie v. 1250) est un mathématicien italien. Fibonacci (de son nom moderne), ou Leonardo Fibonacci, avait, à l époque, pour nom d usage « Leonardo Pisano » (il est… … Wikipédia en Français
Nombre de Fibonacci — Suite de Fibonacci La suite de Fibonacci est une suite d entiers très connue. Elle doit son nom à un mathématicien italien connu sous le nom de Leonardo Fibonacci qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci,… … Wikipédia en Français
Nombres de Fibonacci — Suite de Fibonacci La suite de Fibonacci est une suite d entiers très connue. Elle doit son nom à un mathématicien italien connu sous le nom de Leonardo Fibonacci qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci,… … Wikipédia en Français
Suite de Fibonacci — La suite de Fibonacci est une suite d entiers très connue. Elle doit son nom à Leonardo Fibonacci, dit Leonardo Pisano, un mathématicien italien du XIIIe siècle qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci,… … Wikipédia en Français
Suite de fibonacci — La suite de Fibonacci est une suite d entiers très connue. Elle doit son nom à un mathématicien italien connu sous le nom de Leonardo Fibonacci qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci, décrit la croissance d… … Wikipédia en Français
Séquence de Fibonacci — Suite de Fibonacci La suite de Fibonacci est une suite d entiers très connue. Elle doit son nom à un mathématicien italien connu sous le nom de Leonardo Fibonacci qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci,… … Wikipédia en Français
Leonardo Fibonacci — Naissance 1175 Pise (Italie) Décès 1250 Pise (Italie) Nationalité … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Mot de Fibonacci

Sommaire

Définition