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 $(b_{n})_{n\geq 0}$ composée de $0$ et de $1$ définie par :

$b_{n}=1$ si la représentation binaire de $n$ ne contient pas de bloc composé d'un nombre impair de $0$;

$b_{n}=0$ sinon.

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

La suite commence en $n=0$; 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 $1$ arrive en l'état $a$ si et seulement c'est le développement binaire d'un entier $n$ tel que $b_{n}=1$. Le langage reconnu par l'automate a pour expression rationnelle l'expression $(00+1)^{*}$.

Les termes $b_{n}$ s'évaluent aussi par récurrence. Posons $n=^{j}m$, où $m$ n'est pas divisible par $4$. Alors on a :

$b_{n}={\begin{cases}0&{\text{si }}m{\text{ est pair}}\\b_{(m-1)/2}&{\text{si }}m{\text{ est impair}}.\end{cases}}$

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

$b_{2n+1}=b_{n}$

$b_{4n}=b_{n}$

$b_{4n+2}=0$

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

Le mot infini de Baum et Sweet

$1101|1001|0100|1001|1001|0000|0100|1001\cdots$

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

${\begin{array}{lcl}a&\mapsto &ab\\b&\mapsto &bc\\c&\mapsto &bd\\d&\mapsto &dd\\\end{array}}$

à partir de a. Ceci donne $a,ab,abcb,abcbbdcb,\ldots$ et enfin :

$abcb|bdcb|cbdd|bdcb|bccb|dddd|\cdots$

On applique enfin le morphisme lettre-à-lettre qui envoie $a$ et $b$ sur $1$, et $c$ et $d$ sur $0$.

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

La série

$b(X)=\sum _{n=0}^{\infty }b_{n}X^{n}$

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

$b(X)=\sum _{n=0}^{\infty }b_{n}X^{2n+1}+\sum _{n=0}^{\infty }b_{n}X^{4n}=Xb(X^{2})+b(X^{4})$

donc $Y=b(X)$ est solution de l'équation sur $F_{2}$

$Y^{3}+XY+1=0$.

Références

• (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 $2$ », Ann. of Math. (2), vol. 103, n^o 3,‎ 1976, p. 593-610
• Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences : Theory, Applications, Generalizations, Cambridge University Press, 2003, 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,‎ 2019, p. 81–98 (DOI 10.1016/j.tcs.2019.03.041).

Lien externe

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