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 :
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![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Baum-Sweet.png/220px-Baum-Sweet.png)
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 développement 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- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Baum–Sweet sequence » (voir la liste des auteurs).
- 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 : Theory, Applications, Generalizations, Cambridge University Press, , 571 p. (ISBN 978-0-521-82332-6, zbMATH 1086.11015, lire en ligne)
- Łukasz Merta, « Composition inverses of the variations of the Baum–Sweet sequence », Theoretical Computer Science, vol. 784, , p. 81–98 (DOI 10.1016/j.tcs.2019.03.041).
Lien externe
modifier(en) Eric W. Weisstein, « Baum–Sweet Sequence », sur MathWorld