Nombre de Motzkin

Les M 4 = 9 {\displaystyle M_{4}=9} façons de choisir des cordes, pour 4 points.
Les M 4 = 9 {\displaystyle M_{4}=9} arbres unaires-binaires, pour 4 arcs. Les arbres sont en bijection avec les cercles.
Les M 4 = 9 {\displaystyle 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 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 {\displaystyle M_{n}} d'indice n {\displaystyle n} est le nombre de façons de choisir des cordes ne se coupant pas, parmi les cordes reliant n {\displaystyle n} points disposés sur un cercle. Les nombres de Motzkin satisfont la relation de récurrence suivante :

M n + 1 = M n + ∑ i = 0 n − 1 M i M n − 1 − i {\displaystyle M_{n+1}=M_{n}+\sum _{i=0}^{n-1}M_{i}M_{n-1-i}}

Les nombres de Motzkin correspondent à la suite A001006 de l'OEIS et les premiers de ces nombres sont:

Nombres de Motzkin
n {\displaystyle n} 0 1 2 3 4 5 6 7 8 9 10 11
M n {\displaystyle M_{n}} 1 1 2 4 9 21 51 127 323 835 2188 5798


Propriétés et comportement asymptotique

Série génératrice

Commençons par démontrer la relation de récurrence énoncée dans l'introduction. Parmi n+1 points disposés sur un cercle, choisissons-en un, soit P. Le nombre de façons de choisir des cordes ne se coupant pas et joignant des points choisis parmi les n+1 points en question et tous distincts de P est égal à M n {\displaystyle M_{n}} . D'autre part, si pour j dans {1, 2, ..., n}, P j {\displaystyle P_{j}} désigne le j-ième point après P dans un sens fixé de parcours du cercle, le nombre de façons de choisir des cordes possédant les propriétés voulues et telles qu'une de ces cordes soit la corde P P j {\displaystyle PP_{j}} est le nombre de façons de choisir d'une part un ensemble de cordes convenable relativement aux points P 1 , . . . , P j − 1 {\displaystyle P_{1},...,P_{j-1}} et d'autre part un ensemble de cordes convenable relativement aux points P j + 1 , . . . , P n {\displaystyle P_{j+1},...,P_{n}} . Ces deux choix sont indépendants l'un de l'autre, le nombre de façons de faire le premier est M j − 1 , {\displaystyle M_{j-1},} le nombre de façons de faire le second est M n − j {\displaystyle M_{n-j}} , donc le nombre de façons de faire les deux choix est M j − 1 M n − j {\displaystyle M_{j-1}M_{n-j}} , d'où

M n + 1 = M n + ∑ j = 1 n M j − 1 M n − j {\displaystyle M_{n+1}=M_{n}+\sum _{j=1}^{n}M_{j-1}M_{n-j}} .

Jointe à M 0 = 1 , {\displaystyle M_{0}=1,} cette relation détermine les nombres de Motzkin. Soit

M ( z ) = M 0 + M 1 z + ⋯ + M n z n + ⋯ = 1 + z + 2 z 2 + 4 z 3 + 9 z 4 + ⋯ {\displaystyle M(z)=M_{0}+M_{1}z+\cdots +M_{n}z^{n}+\cdots =1+z+2z^{2}+4z^{3}+9z^{4}+\cdots }

la série génératrice des nombres de Motzkin. La relation de récurrence exprime que cette série satisfait l'équation[1] suivante :

M ( z ) = 1 + z M ( z ) + z 2 M ( z ) 2 {\displaystyle M(z)=1+zM(z)+z^{2}M(z)^{2}} .

De cette équation, on déduit

M ( z ) = 1 − z − ( 1 − 2 z − 3 z 2 ) 1 / 2 2 z 2 , {\displaystyle M(z)={\frac {1-z-(1-2z-3z^{2})^{1/2}}{2z^{2}}},}

et en développant ( 1 − 2 z − 3 z 2 ) 1 / 2 = ∑ n ≥ 0 ( 1 / 2 n ) ( − 2 z − 3 z 2 ) n {\displaystyle (1-2z-3z^{2})^{1/2}=\sum _{n\geq 0}{1/2 \choose n}(-2z-3z^{2})^{n}} , on obtient la formule explicite

M n = 1 2 n + 2 ∑ n + 2 2 ≤ j ≤ n + 2 ( j n + 2 − j ) 3 n + 2 − j C j − 1 , {\displaystyle M_{n}={\frac {1}{2^{n+2}}}\sum _{{\frac {n+2}{2}}\leq j\leq n+2}{j \choose n+2-j}3^{n+2-j}C_{j-1},}

où C j − 1 {\displaystyle C_{j-1}} est le nombre de Catalan 1 j ( 2 j − 2 j − 1 ) . {\displaystyle {\frac {1}{j}}{2j-2 \choose j-1}.}

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

M n ∼ 3 2 π n − 3 / 2 3 n + 1 {\displaystyle M_{n}\sim {\frac {\sqrt {3}}{2{\sqrt {\pi }}}}n^{-3/2}3^{n+1}}

La série génératrice M ( z ) {\displaystyle M(z)} vérifie

M ( z ) 2 = 1 1 − 2 z M ( z 2 1 − 2 z ) . {\displaystyle M(z)^{2}={\frac {1}{1-2z}}M\left({\frac {z^{2}}{1-2z}}\right).}

Formules diverses

Il y a d'autres expressions explicites des nombres de Motzkin que celle qui a été déduite plus haut d'une équation satisfaite par la série génératrice.

On a par exemple[3]

M n = ∑ i ( − 1 ) n − i ( n i ) C i + 1 {\displaystyle M_{n}=\sum _{i}(-1)^{n-i}{\binom {n}{i}}C_{i+1}} .

D'autre part, en appliquant le théorème d'inversion de Lagrange à la série génératrice, on obtient[4] l'expression

M n − 1 = 1 n ∑ k ( n k ) ( n − k k + 1 ) {\displaystyle M_{n-1}={\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 = 2 n + 3 n + 3 M n + 3 n n + 3 M n − 1 {\displaystyle M_{n+1}={\frac {2n+3}{n+3}}M_{n}+{\frac {3n}{n+3}}M_{n-1}} .

Il n'est pas évident a priori que les nombres définis par cette relation soient entiers[5],[6].

Définitions équivalentes

Arbre unaire-binaire

Le nombre de Motzkin M n {\displaystyle 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 {\displaystyle 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

Le nombre de Motzkin M n {\displaystyle M_{n}} est également le nombre de chemins reliant le point ( 0 , 0 ) {\displaystyle (0,0)} au point ( n , 0 ) {\displaystyle (n,0)} , constitué de pas Nord-Est ( 1 , 1 ) {\displaystyle (1,1)} ou Sud-Est ( 1 , − 1 ) {\displaystyle (1,-1)} ou Est ( 1 , 0 ) {\displaystyle (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 (resp. descendant) la visite d'un enfant gauche (resp. droit) quand il y en a deux, et par un pas horizontal la visite d'un enfant unique.

Le nombre de Motzkin M n {\displaystyle M_{n}} est également aussi le nombre de suites d'entiers naturels de longueur n − 1 {\displaystyle 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 équivalence 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

Le nombre de Motzkin M n {\displaystyle M_{n}} est égal au nombre de mots de Motzkin de longueur n {\displaystyle n} , c'est-à-dire de mots de longueur n {\displaystyle 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 , x ¯ } {\displaystyle A=\{a,x,{\bar {x}}\}} un alphabet à trois lettres. Le langage de Motzkin M {\displaystyle {\mathcal {M}}} est l'ensemble de mots défini par l'équation

M = ε + a M + x M x ¯ M {\displaystyle {\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 → ε ∣ a S ∣ x S x ¯ S {\displaystyle S\to \varepsilon \mid aS\mid xS{\bar {x}}S}

Les premiers mots du langage rangés par longueur :

n {\displaystyle n}   M n {\displaystyle M_{n}}
0  1 ε {\displaystyle \varepsilon }
1  1 a {\displaystyle a}
2  2 a a , x x ¯ {\displaystyle aa,x{\bar {x}}}
3  4 a a a , a x x ¯ , x a x ¯ , x x ¯ a {\displaystyle aaa,ax{\bar {x}},xa{\bar {x}},x{\bar {x}}a}
4  9 a a a a , a a x x ¯ , a x x ¯ a , x x ¯ a a , x a x ¯ a , a x a x ¯ , x a a x ¯ , x x ¯ x x ¯ , x x x ¯ x ¯ {\displaystyle aaaa,aax{\bar {x}},ax{\bar {x}}a,x{\bar {x}}aa,xa{\bar {x}}a,axa{\bar {x}},xaa{\bar {x}},x{\bar {x}}x{\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 {\displaystyle x} , un pas descendant par la lettre x ¯ {\displaystyle {\bar {x}}} , et un pas horizontal par la lettre a {\displaystyle a} .

Nombres de Motzkin premiers

Les quatre seuls nombres de Motzkin premiers connus sont, d'après la suite A092832 de l'OEIS : 2, 127, 15 511 et 953 467 954 114 363.

Remarques

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.

Notes et références

  1. ↑ Analytic Combinatorics, p. 84 (P. 68 et 88 dans l'édition en ligne.)
  2. ↑ Analytic Combinatorics, p. 279.
  3. ↑ (en) Frank R. Bernhart, « Catalan, Motzkin, and Riordan numbers », Discrete Math., vol. 204, nos 1-3,‎ , p. 73-112 (DOI 10.1016/S0012-365X(99)00054-0), spéc. p. 99.
  4. ↑ Bernhart 1999, p. 102.
  5. ↑ 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,‎ , p. 671-676
  6. ↑ Dans l'article : Martin Klazar et Florian Luca, « On integrality and periodicity of the Motzkin numbers », Aequationes Math., vol. 69, nos 1-2,‎ , 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.

Voir aussi

Bibliographie

  • (en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, (ISBN 0-521-89806-4, lire en ligne)
  • (en) Robert Donaghey et Louis W. Shapiro, « Motzkin numbers », JCTA, vol. 23, no 3,‎ , p. 291-301
  • Christian Krattenthaler et Thomas W. Müller, « Motzkin numbers and related sequences modulo powers of 2 », European Journal of Combinatorics, vol. 73,‎ , p. 114–137 (DOI 10.1016/j.ejc.2018.05.004).

Articles connexes

  • icône décorative Portail des mathématiques