Suite de Baum-Sweet

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, et en combinatoire des mots, la suite de Baum-Sweet ou suite de Baum et Sweet est une suite automatique composée de et de définie par :

si la représentation binaire de ne contient pas de bloc composé d'un nombre impair de ;
sinon.

Par exemple, parce que la représentation binaire de 4 est 100 et ne contient qu'un bloc de deux 0; en revanche, parce que la représentation binaire de 5 est 101 et contient un bloc formé d'un seul 0. De même, , parce que la représentation binaire de 76 est 1001100.

La suite commence en ; ses premiers termes sont :

1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1 ... (c'est la suite A086747 de l'OEIS)

La suite est nommée d'après Leonard E. Baum et Melvin M. Sweet qui ont été les premiers à l'étudier en 1976.

Propriétés[modifier | modifier le code]

Automate pour la suite de Baum et Sweet.

La suite de Baum et Sweet est 2-automatique. Elle peut donc être engendrée par un automate fini. Dans l'automate ci-contre, un mot commençant par arrive en l'état si et seulement c'est le dveloppement binaire d'un entier tel que . Le langage reconnu par l'automate a pour expression rationnelle l'expression .

Les termes s'évaluent aussi par récurrence. Posons , où n'est pas divisible par . Alors on a :

Cette relation équivaut au calcul du 2-noyau. On a en effet :

Le 2-noyau est donc composé de 3 suites.

Le mot infini de Baum et Sweet

est morphique. On itère d'abord le morphisme 2-uniforme :

à partir de a. Ceci donne et enfin :

On applique enfin le morphisme lettre-à-lettre qui envoie et sur , et et sur .

Le mot de Baum et Sweet contient des plages arbitrairement longues de  : ce mot n'est donc pas uniformément récurrent. En revanche, le mot ne contient pas de facteur composé de trois consécutifs.

La série

s'écrit, avec les relations de récurrence, sous la forme :

donc est solution de l'équation sur

.

Références[modifier | modifier le code]

  • Leonard E. Baum et Melvin M. Sweet, « Continued fractions of algebraic power series in characteristic  », Ann. of Math. (2), vol. 103, no 3,‎ , p. 593-610
  • Jean-Paul Allouche et Jeffrey Shallit Automatic Sequences Cambridge University Press, 2003.

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Baum–Sweet Sequence », MathWorld