Suite de Baum-Sweet

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

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

Lien externe

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

  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.