Nombre de Motzkin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Les M_4=9 façons de choisir des cordes, pour 4 points.
Les M_4=9 arbres unaires-binaires, pour 4 arcs. Les arbres sont en bijection avec les cercles.
Les M_4=9 chemins de Motzkin, pour 4 pas. Les chemins sont en bijection avec les arbres.

En mathématiques, et plus particulièrement en combinatoire, les nombres de Motzkin forment une suite d'entiers naturels utilisée dans divers problèmes de dénombrement. Ils sont nommés ainsi d'après le mathématicien d'origine allemande Théodore Motzkin (1908-1970). Les nombres de Motzkin ont de nombreuses applications en géométrie, combinatoire et théorie des nombres.

Le nombre de Motzkin M_n d'indice n est le nombre de façon de choisir des cordes ne se coupant pas, parmi les cordes reliant n points disposés sur un cercle. Les nombres de Motzkin satisfont la relation de récurrence suivante :

M_{n+1}=M_n+\sum_{i=0}^{n-1}M_iM_{n-1-i}

Les premiers nombres de Motzkin sont, d'après la suite A001006 de l'OEIS :

Nombres de Motzkin
n 0 1 2 3 4 5 6 7 8 9 10 11
M_n 1 1 2 4 9 21 51 127 323 835 2188 5798


Propriétés et comportement asymptotique[modifier | modifier le code]

Série génératrice[modifier | modifier le code]

Soit

M(z)=M_0+M_1z+\cdots+M_nz^n+\cdots =1+z+2z^2+4z^3+ 9z^4+\cdots

la série génératrice des nombres de Motzkin. Elle satisfait l'équation[1] suivante :

M(z)=1+zM(z)+z^2M(z)^2

Par identification des coefficients, on obtient la formule de définition donnée dans l'Introduction. On peut la justifier comme suit : fixons un de n+1 point du cercle. Si aucune corde ne lie ce point, on peut l'identifier avec son voisin (de gauche par exemple), et le nombre de choix de cordes est M_n. Si au contraire une corde lie ce point à un autre point, la paire découpe le cercle en deux cercles plus petits, où à nouveau on identifie les deux extrémités de la corde. Le nombre total de points sur les deux cercles est donc n-1. Ceci donne le deuxième terme de la relation.

L'étude de la série génératrice permet d'obtenir l'expression suivante pour le comportement asymptotique[2] :

M_n \sim \frac {\sqrt3} {2\sqrt\pi} n^{-3/2} 3^{n+1}

Formules diverses[modifier | modifier le code]

Le coefficient M_n admet, par le théorème d'inversion de Lagrange appliqué à la série génératrice, l'expression suivante :

M_n=\frac 1 n \sum_k \binom n k \binom {n-k} {k-1}

Les nombres de Motzkin vérifient aussi la relation de récurrence linéaire à coefficients polynomiaux suivante :

M_{n+1}=\frac{2n+3}{n+3}M_n+\frac{3n}{n+3}M_{n-1}

Il n'est pas évident que les nombres définis par cette relation sont entiers[3],[4]!

Définitions équivalentes[modifier | modifier le code]

Arbre unaire-binaire[modifier | modifier le code]

Le nombre de Motzkin M_n est aussi le nombre d'arbres unaires-binaires (c'est-à-dire d'arbres planaires enracinés où chaque nœud a un ou deux enfants) à n arcs. On peut voir cela directement, par interprétation de la relation de récurrence, ou aussi en établissant une bijection entre les cercles à cordes et ces arbres. Choisissons à nouveau un point sur un cercle. S'il n'est pas lié par une corde, on lui fait correspondre la racine d'un arbre avec un seul fils qui correspond au cercle fusionné. Sinon, la corde découpe le cercle en deux parties, correspondant aux sous-arbres gauche et droit d'un arbre dont la racine a deux fils.

Chemin de Motzkin[modifier | modifier le code]

Le nombre de Motzkin M_n est également le nombre de chemins reliant le point (0,0) au point (n,0), constitué de pas Nord-Est (1,1) ou Sud-Est (1,-1) ou Est (1,0), le chemin devant se trouver entièrement dans le quadrant supérieur droit d'un repère. Un tel chemin est un chemin de Motzkin. La correspondance entre arbres unaires-binaires et chemins de Motzkin s'obtient en effectuant un parcours préfixe sur l'arbre, et en notant par un pas montant (descendant) la visite d'un enfant gauche (droit) quand il y en a deux, et par un pas horizontal la visite d'un enfant unique.

Le nombre de Motzkin M_n est également aussi le nombre de suites d'entiers naturels de longueur n-1 vérifiant les deux conditions suivantes: le premier et le dernier éléments valent 0 ou 1; la différence entre deux éléments consécutifs est -1, 0 ou 1. Cette équivalent s'obtient en considérant les ordonnées des points d'un chemin de Motzkin, sauf les deux points extrêmes, et en notant la différence des ordonnées de deux points consécutifs.

Mot de Motzkin[modifier | modifier le code]

Le nombre de Motzkin M_n est égal au nombre de mots de Motzkin de longueur n, c'est-à-dire de mots de longueur n du langage appelé langage de Motzkin. Ce langage est une extension du langage de Dyck sur une paire de parenthèses, obtenu par mélange des mots de Dyck avec des mots sur une nouvelle lettre. Plus précisément, soit A=\{a,x,\bar x\} un alphabet à trois lettres. Le langage de Motzkin \mathcal M est l'ensemble de mots défini par l'équation

{\mathcal M} =\varepsilon + a{\mathcal M} + x {\mathcal M}\bar x{\mathcal M}

ou, de manière équivalent, engendré par la grammaire algébrique

S\to \varepsilon\mid aS\mid  xS\bar xS

Les premiers mots du langage sont, rangés par longueur :

n  M_n
0  1 \varepsilon
1  1 a
2  2 aa, x\bar x
3  4 aaa,ax\bar x, xa\bar x,x\bar x a
4  9 aaaa, aa x\bar x, ax\bar x a, x\bar x aa, xa\bar x a, axa\bar x, xaa\bar x, x\bar xx\bar x, xx\bar x\bar x

La correspondance entre mots de Motzkin et chemin de Motzkin s'obtient en notant un pas montant par la lettre x, un pas descendant par la lettre \bar x, et un pas horizontal par la lettre a.

Nombres de Motzkin premiers[modifier | modifier le code]

Les seuls nombres de Motzkin connus qui sont des premier sont, d'après la suite A092832 de l'OEIS, les nombres :

2, 127, 15 511, 953 467 954 114 363

Notes[modifier | modifier le code]

Donaghey et Shapiro (1977) illustrent l'étroite parenté entre les nombres de Motzkin et les nombres de Catalan par quatorze applications différentes des nombres de Motzkin en mathématiques. Depuis, de nombreuses occurrences des nombres de Motzkin ont été trouvés en combinatoire, en informatique théorique et en mathématiques : MathSciNet recense plus de 100 articles ayant le mot Motzkin dans le titre.

Références[modifier | modifier le code]

  1. Analytic Combinatorics, p. 84
  2. Analytic Combinatorics, p. 279
  3. Une preuve combinatoire est donnée dans : Serge Dulucq et Jean-Guy Penaud, « Interprétation bijective d'une récurrence des nombres de Motzkin », Discrete Math., vol. 256, no 3,‎ 2002, p. 671-676
  4. Dans l'article : Martin Klazar et Florian Luca, « On integrality and periodicity of the Motzkin numbers », Aequationes Math., vol. 69, no 1-2,‎ 2005, p. 68-75, les auteurs prouvent que les seules suites à valeurs entières qui satisfont cette relation sont les multiples de la suite des nombres de Motzkin.

Bibliographie[modifier | modifier le code]

  • (en) Robert Donaghey et Louis W. Shapiro, « Motzkin numbers », JCTA, vol. 23, no 3,‎ 1977, p. 291-301

Voir aussi[modifier | modifier le code]