Suite de Prouhet-Thue-Morse

Suite de Prouhet-Thue-Morse

En mathématiques, en informatique théorique, en combinatoire des mots et ses applications, la suite de Thue-Morse (appelée souvent suite de Prouhet-Thue-Morse chez les francophones) est une suite binaire. Elle commence par :

t = 01101001100101101001011001101001...

Cette suite infinie est la suite A010060 de l’OEIS.

Sommaire

Définition

Il y a plusieurs manières équivalentes de définir cette suite.

Relation de récurrence

Construction de la suite de Prouhet-Thue-Morse.

La suite de Prouhet-Thue-Morse est la suite t = (tn) qui satisfait t0 = 0 et

t2n = tn
t2n + 1 = 1 − tn

pour tous les entiers naturels n. Cette définition peut s'interpréter comme suit: si l'on ne conserve, dans la suite t, que les termes d'indices pairs, on retrouve la suite t; si en revanche on ne garde que les termes d'indices impairs, on obtient la suite opposée, où les 0 et 1 ont été échangés.

Une autre relation de récurrence

Soient un et vn les suites de mots définis par:

\begin{array}{ll}u_{0}&=0\\u_{n+1}&=u_nv_n\end{array} \quad\begin{array}{ll}v_{0}&=1\\v_{n+1}&=v_nu_n\end{array}

Alors

t=\lim_{n\to\infty}u_n=0v_1v_2\cdots v_n\cdots

Un produit infini

La suite peut être aussi définie par:

\prod_{i=0}^{\infty} (1 - x^{2^{i}}) = \sum_{j=0}^{\infty} (-1)^{t_j} x^{j} \mbox{,} \!

Histoire

La suite de Prouhet-Thue-Morse a été décrite pour la première fois par le mathématicien français Eugène Prouhet en 1851. Il l'a utilisé pour donner une solution à un problème de théorie des nombres qui s'appelle le problème de Prouhet-Tarry-Escott (en).

Le mathématicien norvégien Axel Thue l'a découverte et utilisée dans un article publié en 1906 qui est l'article fondateur de la combinatoire des mots. Cet article a été longtemps méconnu. La suite a été redécouverte par Marston Morse en 1921. Morse l'a utilisée pour donner un exemple d'une suite uniformément récurrente non périodique, résolvant ainsi un problème de géométrie différentielle.

La suite a été redécouverte indépendamment plusieurs fois, pas toujours par des mathématiciens professionnels. Par exemple, Max Euwe, un champion d'échecs et professeur de mathématiques, l'a découverte en 1929 pour une application aux échecs, prouvant, par ce biais, qu'il existe des parties infinies ne comportant pas de répétition des trois mêmes coups. En 1944, Marston Morse et Gustav Hedlund (de) ont développé cet aspect.

Propriétés

  • La suite de Prouhet-Thue-Morse est sans cube: aucun bloc n'est répété trois fois consécutivement. Axel Thue a prouvé que la suite est même sans chevauchement: aucun bloc n'est de la forme axaxa, où a est un des symboles 0 ou 1 et x est un bloc.
\tau = \sum_{i=0}^{\infty} \frac{t_i}{2^{i+1}} = 0,412454033640 \ldots

C'est un nombre transcendant.

Références

  • Allouche, J.-P.; Shallit, J. O., Automatic sequences, Cambridge University Press, 2003.

Liens externes



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Suite de Prouhet-Thue-Morse de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Suite de prouhet-thue-morse — En mathématiques et ses applications, la suite de Prouhet Thue Morse (appelé souvent suite de Thue Morse chez les anglo saxons) est une certaine suite binaire. Elle commence par : 0 1 10 1001 10010110 1001011001101001... (Les espaces ne sont …   Wikipédia en Français

  • Suite Prouhet-Thue-Morse — Suite de Prouhet Thue Morse En mathématiques et ses applications, la suite de Prouhet Thue Morse (appelé souvent suite de Thue Morse chez les anglo saxons) est une certaine suite binaire. Elle commence par : 0 1 10 1001 10010110… …   Wikipédia en Français

  • Constante De Prouhet-Thue-Morse — En mathématiques et dans ses applications, la constante de Prouhet Thue Morse est le nombre dont le développement binaire est la suite de Prouhet Thue Morse. C’est à dire, où ti est la suite de Prouhet Thue Morse. La série génératrice pour ti est …   Wikipédia en Français

  • Constante de prouhet-thue-morse — En mathématiques et dans ses applications, la constante de Prouhet Thue Morse est le nombre dont le développement binaire est la suite de Prouhet Thue Morse. C’est à dire, où ti est la suite de Prouhet Thue Morse. La série génératrice pour ti est …   Wikipédia en Français

  • Constante de Prouhet-Thue-Morse — En mathématiques et dans ses applications, la constante de Prouhet Thue Morse est le nombre dont le développement binaire est la suite de Prouhet Thue Morse. C’est à dire, où ti est la suite de Prouhet Thue Morse. La série génératrice pour ti est …   Wikipédia en Français

  • Morse — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Un morse. Le morse est un mammifère marin, mais l appellation peu …   Wikipédia en Français

  • Axel Thue — (19 février 1863 7 mars 1922) est un mathématicien norvégien. En 1909, il publia un article important avec le théorème suivant, essentiel pour l étude des équations diophantiennes : Théorème Si f(x;y) est un polynôme homogène à coefficients… …   Wikipédia en Français

  • Marston Morse — Pour les articles homonymes, voir Marston et Morse. H. C. Marston Morse Marston Morse en 1965 (collection du MFO) Naissance …   Wikipédia en Français

  • Morses — Morse Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Le morse est un mammifère marin. Le nom Morse peut faire référence à : Patronymes Anthony P. Morse, mathématicien ; voir notamment la… …   Wikipédia en Français

  • Combinatoire des mots — Construction de la suite de Prouhet Thue Morse. La combinatoire des mots est une branche des mathématiques et de l informatique théorique qui applique l analyse combinatoire aux mots finis ou infinis. Cette branche s est développée à partir de… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”