Suite de Tribonacci

Une suite de Tribonacci est une suite d'entiers dont la relation de récurrence est inspirée de celle de la suite de Fibonacci : chaque terme est la somme des trois termes qui le précèdent (dans une suite de Fibonacci, chaque terme est la somme des deux termes qui le précèdent).

Le terme de Tribonacci est un néologisme formé de tri (récurrence à trois termes) et de bonacci (en allusion au mathématicien Fibonacci). Il existe de même des suites de Tetranacci où chaque terme est la somme des 4 termes qui le précèdent et même des suites de Modèle:Mvar-bonacci où chaque terme est la somme des Modèle:Mvar termes qui le précèdent.

Un nombre tribonaccique est un entier de la suite de Tribonacci.

Une suite de Tribonacci est aussi une suite de "mots" de 3 lettres construite à l'aide de la substitution de Tribonacci : a donne ab, b donne ac et c donne a.

Étude mathématique

La suite de Tribonacci étudiée ici est définie par :

<math> T_0 = 0</math>, <math> T_1 = 1</math>, <math> T_2 = 1</math> ;
pour tout entier naturel Modèle:Mvar, <math> T_{n+3} = T_{n+2} + T_{n+1} + T_n</math>.

Les dix premiers termes sont donc : 0, 1, 1, 2, 4, 7, 13, 24, 44, 81 (Modèle:OEIS décalée d'un cran).

L'étude des suites récurrentes linéaires permet de dire que cette suite est combinaison linéaire des trois suites <math>(r_1^n)</math>, <math>(r_2^n)</math>, <math>(r_3^n)</math> où les <math> r_i</math> sont les trois racines du polynôme <math>X^3 -X^2 -X- 1</math>.

La racine réelle (environ égale à 1,839 <ref name=OEIS58265>Voir la Modèle:OEIS.</ref>) est appelée constante de Tribonacci et correspond à la limite du quotient de deux termes consécutifs. Les formules de Cardan en donnent une valeur exacte <ref name=OEIS58265/> :
<math>r_1=\alpha_3=\frac{\sqrt[3]{19+3\sqrt{33}}+\sqrt[3]{19-3\sqrt{33}}+1}3</math>.
Les deux racines complexes sont conjuguées l'une de l'autre et de module inférieur à 1.

Le terme général de la suite est alors :

<math> T_n = a_1r_1^n + a_2r_2^n + a_3r_3^n</math> où les <math>a_i</math> sont donnés par les formules suivantes :

mais on a aussi, uniquement en fonction de <math>\alpha_3</math> <ref name=":0">Modèle:Article</ref> :

<math>T_n=\left\lfloor\frac{\alpha_3^{n-1}(\alpha_3-1)}{4\alpha_3-6}\right\rceil,</math> où et <math>\left\lfloor .\right\rceil</math> désigne la fonction "entier le plus proche".

On peut aussi travailler sur la série génératrice de cette suite, c’est-à-dire la série formelle :

<math>F=\sum T_nX^n</math>.

La série génératrice de la suite <math>T_{n-1}</math> est alors XF, celle de <math>T_{n-2}</math> est <math>X^2F</math> et celle de <math>T_{n-3}</math> est <math> X^3F</math> ; la relation de récurrence <math> T_n= T_{n-1} + T_{n-2} + T_{n-3}</math>, valable pour tout n supérieur ou égal à 3, assure que

<math>F = XF + X^2F + X^3F + X + X^2 - X^2</math>.

Les termes en complément correspondent aux 3 premiers termes des suites. Il suffit alors de résoudre cette équation. La fonction génératrice de la suite est donc :

<math> F = \frac{X}{1-X-X^2-X^3} = X + X^2 + 2X^3 + 4X^3 + 7X^4 + \dots</math>.

Modèle:Lien a prouvé en 1980<ref>Modèle:Article.</ref> qu'il existe une partition de ℕ en deux ensembles dont la somme ne contient aucun élément de la suite de Tribonacci.

Interprétation combinatoire

Modèle:Math est égal au nombre de suites finies d'entiers égaux à 1, 2 ou 3 dont la somme est égale à Modèle:Mvar , c'est-à-dire le nombre de compositions de Modèle:Mvar formées à partir de ces entiers ; par exemple <math>T_4=4</math> car 3 s'écrit <math>1+1+1,1+2,2+1,\text{ou }3</math> <ref name="Baez">{{#invoke:Langue|indicationDeLangue}} John C. Baez, One-bonacci, Two-bonacci, Three-bonacci, Four..., 12/12/2003</ref>^,<ref>Modèle:Lien web</ref>.

De façon imagée, Modèle:Math est le nombre de façons de vider un tonneau de Modèle:Mvar litres à l'aide de bouteilles de un, deux, ou trois litres, ou le nombre de façons de découper un segment de longueur Modèle:Mvar en segments de longueur 1, 2 ou 3.

Démonstration : les compositions de Modèle:Mvar se terminant par 1 sont obtenues en ajoutant 1 à la fin d'une composition de <math>n-1</math>, celles se terminant par 2 sont obtenues en ajoutant 2 à la fin d'une composition de <math>n-2</math>, celles se terminant par 3 sont obtenues en ajoutant 3 à la fin d'une composition de <math>n-3</math> , donc le nombre <math>C_n</math> de composition de Modèle:Mvar vérifie <math>C_n=C_{n-1}+C_{n-2}+C_{n-3}</math>. De plus, <math>C_0=T_1=1</math> (la composition vide), <math>C_1=T_2=1 </math> (la composition (1)), <math>C_2=T_3=2 </math> (les compositions (1,1) et (2)), ce qui montre la relation.

De manière plus générale<ref name="Baez" />, le terme d'indice Modèle:Mvar + 1 d'une suite de Modèle:Mvar-bonacci (chaque terme est la somme des Modèle:Mvar précédents, les termes d'indice <math>0,1,2,3,\cdots,k-1</math> étant égaux à <math>\left(0,1,1,2,\cdots,2^{k-3}\right)</math> correspond au nombre de compositions de Modèle:Mvar formées à partir des entier de 1 à Modèle:Mvar.

Suite de mots de Tribonacci

C'est la suite de mots définie par :

M(1) = a

et par la substitution de Tribonacci suivante :

a donne ab, b donne ac et c donne a

Nous obtenons alors la suite de mots suivants : a, ab, ab|ac, abac|ab|a, abacaba|abac|ab, abacabaabacab|abacaba|abac... On s'aperçoit ainsi que chaque mot est obtenu comme la concaténation des 3 mots précédents. Il n'est donc pas surprenant que la longueur de ces mots soit une suite d'entiers de Tribonacci. Le mot infini obtenu à la limite est le mot infini de Tribonacci. C'est un mot purement morphique.

La suite de mots intervient dans la construction de la fractale de Rauzy.