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 (b_n)_{n\ge0} 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[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 1 arrive en l'état a si et seulement c'est le dveloppement 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=^jm, 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, abcb bdcb,\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_nX^n

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

b(X)=\sum_{n=0}^\infty b_nX^{2n+1}+ \sum_{n=0}^\infty b_nX^{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[modifier | modifier le code]

  • Leonard E. Baum et Melvin M. Sweet, « Continued fractions of algebraic power series in characteristic 2 », Ann. of Math. (2), vol. 103, no 3,‎ 1976, 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