Discussion:Nombre de Motzkin

La relation entre les suites d'entiers et le chemin dans un repère me paraît évidente, mais le lien avec les cordes me semble plus complexe. Il serait peut-être intéressant d'ajouter des indices concernant ce dernier pont, ou modifier le troisième exemple pour faire apparaître une autre manifestation des points de Motskin qui n'a pas de lien direct avec les deux autres (c'est un point de vue). Qu'en pensez-vous?

J'ai ajouté une esquisse de preuve de la correspondance, et des dessins.--ManiacParisien (d) 13 février 2012 à 10:17 (CET)

modèle de sources et identifiant Stanley

Bonjour, j'allais remplacer la source Enumerative Combinatorics par le modèle que j'ai créé pour cet ouvrage mais je vois qu'il y a un identifiant : 'stanley'... Où est-il utilisé ? Puis-je faire la modif ? Amicalement, --Roll-Morton (d) 8 décembre 2012 à 19:06 (CET)

Bonjour, bonne question ! Le livre n'est cité nulle part dans le texte ! Si on enlevait simplement la référence ? Je le fais, je crois qu'il n'y a pas de problème. Merci. --ManiacParisien (d) 8 décembre 2012 à 19:46 (CET)

La section « Série génératrice »

La section Série génératrice commence comme ceci :

« Soit

$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. Elle satisfait l'équation suivante :

$M(z)=1+zM(z)+z^{2}M(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. »

Il me semble qu'en fait, l'équation satisfaite par la série génératrice (équation qu'on peut écrire $1+(z-1)M(z)+z^{2}M(z)^{2}=0$) se déduit de la relation par récurrence donnée dans l'introduction. On doit donc commencer par démontrer cette relation de récurrence, et c'est d'ailleurs ce qui est fait dans l'article.

Pour ma part, je préférerais rédiger cette démonstration sans parler d'identification entre points ni d'un cercle plus petit que le cercle de départ. Je dirais ceci :

« 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}$. D'autre part, si pour j dans {1, 2, ..., n}, $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 $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}$ et d'autre part un ensemble de cordes convenable relativement aux points $P_{j+1},...,P_{n}$. Ces deux choix étant indépendants l'un de l'autre, le nombre de façons de les faire tous deux est $M_{j-1}M_{n-j}$, donc

$M_{n+1}=M_{n}+\sum _{j=1}^{n}M_{j-1}M_{n-j}$

ou encore

$M_{n+1}=M_{n}+\sum _{i=0}^{n-1}M_{i}M_{n-1-i}.$ »

Comme je l'ai noté, cela permet de prouver la relation

$1+(z-1)M(z)+z^{2}M(z)^{2}=0$

d'où

$M(z)={\frac {1-z-(1-2z-3z^{2})^{1/2}}{2z^{2}}}.$

Il y a d'ailleurs quelque chose qui me semble curieux. En développant

$(1-2z-3z^{2})^{1/2}=\sum _{n\geq 0}{1/2 \choose n}(-2z-3z^{2})^{n}$, on trouve la formule explicite

$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}$ est le nombre de Catalan

${\frac {2j-2 \choose j-1}{j}},$

mais cette formule ne semble intéresser personne...

Ceci dit, que pense-t-on de la façon dont je propose de rédiger la démonstration de la relation de récurrence ? Marvoir (discuter) 27 décembre 2015 à 11:50 (CET)

La formule est celle de Doslic et al sur A001006 de OEIS, je crois. Pour la rédaction de la démonstration, la vôtre me convient tout à fait. On attend d’ autres avis ? -- ManiacParisien (discuter) 27 décembre 2015 à 19:39 (CET)

Vous avez raison, j'avais tort de dire que cette formule ne semble intéresser personne. Pour changer la rédaction de la démonstration de la relation de récurrence, on peut attendre d'autres avis, en effet. S'il n'y en a pas d'ici demain soir, je propose de faire le changement sans plus attendre. Marvoir (discuter) 27 décembre 2015 à 19:52 (CET)

Formule douteuse

L'article dit :

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

$M_{n}={\frac {1}{n}}\sum _{k}{\binom {n}{k}}{\binom {n-k}{k-1}}.$ »

Cette formule me semble inexacte. Elle n'a pas de sens pour n = 0 et pour 2, elle donne (en admettant que ${\binom {2}{-1}}=0$)

$M_{2}={\frac {1}{2}}\sum _{k}{\binom {2}{k}}{\binom {2-k}{k-1}}=1,$

ce qui est faux.

Ne faut-il pas plutôt écrire

$M_{n-1}={\frac {1}{n}}\sum _{k}{\binom {n}{k}}{\binom {n-k}{k+1}},$

ce qui concorde avec Frank R. Bernhart, « Catalan, Motzkin, and Riordan numbers », Discrete Mathematics, vol. 204 (1999), p. 73-112, spéc. p. 102, en ligne ? Marvoir (discuter) 28 décembre 2015 à 21:09 (CET)

Retour sur Catalan

Bonjour, je vois dans l'Encyclopédie la formule

a(n) = (3/2)^(n+2) * Sum_{k >= 1} 3^(-k) * Catalan(k-1) * binomial(k, n+2-k).

attribuée à Doslic et al. Elle s'écrirait ici

$M_{n}=(3/2)^{n+2}\sum _{k\geq 1}3^{-k}C_{k-1}{\binom {k}{n+2-k}}$

où $C_{j}$ est le nombre de Catalan

${\frac {1}{j+1}}{\binom {2j}{j}}$.

Elle est plus simple que l'écriture actuelle, mais la même, non ? Je mettrais même le Catalan dans la formule :

$M_{n}=(3/2)^{n+2}\sum _{k\geq 1}{\frac {3^{-k}}{k}}{\binom {2k-2}{k}}{\binom {k}{n+2-k}}$

mais là c'est une affaire de goût (et un TI ?). -- ManiacParisien (discuter) 3 janvier 2016 à 08:59 (CET)

La formule

$M_{n}=(3/2)^{n+2}\sum _{k\geq 1}3^{-k}C_{k-1}{\binom {k}{n+2-k}},$

que vous indiquez plus haut, contient deux fois des puissances de 3. Elle ne me semble donc pas plus simple que la formule donnée dans l'article. Quant à donner cette formule en y remplaçant le nombre de Catalan par son expression $C_{j}={\frac {1}{j+1}}{\binom {2j}{j}}$, je n'y ai pas d'objection, mais je donnerais aussi la forme avec le nombre de Catalan, car ${\binom {2j}{j}}$ n'est tout de même pas n'importe quel nombre combinatoire, et vu les nombreuses propriétés des nombres de Catalan, il n'est pas impossible que l'expression de M_n faisant intervenir les nombres de Catalan suggère des propriétés des nombres de Motzkin. J'avais indiqué le développement $(1-2z-3z^{2})^{1/2}=\sum _{n\geq 0}{1/2 \choose n}(-2z-3z^{2})^{n}$, que vous avez supprimé. Il me semblait que c'était une façon rapide d'indiquer au lecteur qui ne le saurait pas encore comment on explicite la série $(1-2z-3z^{2})^{1/2}$. Marvoir (discuter) 3 janvier 2016 à 10:01 (CET)

D'accord. Je remets la formule du développement, et je ne touche à rien d'autre. Cordialement -- ManiacParisien (discuter) 4 janvier 2016 à 11:52 (CET)

Merci ! Marvoir (discuter) 4 janvier 2016 à 11:58 (CET)

Bonjour, quelqu'un serait-il en mesure de détailler la démonstration à partir de l'usage du binome de Newton. Merci d'avance. — Le message qui précède, non signé, a été déposé par Chrome7845 (discuter), le 27 avril 2020 à 23:29 (CEST)

Nombre de Motzkin

La démonstration manque d'éléments à partir de l'usage du binome de newton — Le message qui précède, non signé, a été déposé par Chrome7845 (discuter), le 28 avril 2020 à 12:47 (CEST)