Discussion:Nombre de Catalan

J'hésite à renommer en Nombres de Catalan, on emploie plus souvent le pluriel et c'est surtout la suite de ces nombres qui compte. Autre avis ? (:Julien:) ✒ 4 avril 2007 à 22:05 (CEST)

le pluriel me semble également plus approprié--Chassaing 13 juillet 2009 à 00:48 (CEST)

combinatoire

ai rajouté 2 exemples mais ne pense pas ajouter la soixantaine d'exemples (!!!!) figurant dans le tome 2 de la première édition de "enumerative combinatorics" de Stanley (j'ai oui dire qu'il y en avait encore plus dans l'edition la plus récente). Par contre je pense rajouter des figures et des liens, et expliciter certaines bijections.--Chassaing 13 juillet 2009 à 00:58 (CEST)

Démonstration de l'équivalence

Cette démonstration serait-elle pertinente ?

$C_{n}={\frac {2n\,!}{n\,!(n+1)\,!}}\sim {\frac {{\sqrt {4\pi n}}\,\left({2n \over {\rm {e}}}\right)^{2n}}{{\sqrt {2\pi n}}\,\left({n \over {\rm {e}}}\right)^{n}{\sqrt {2\pi (n+1)}}\,\left({n+1 \over {\rm {e}}}\right)^{n+1}}}$

$C_{n}\sim {\sqrt {\frac {4\pi n}{4\pi ^{2}n(n+1)}}}{\frac {\left({2n \over {\rm {e}}}\right)^{2n}}{\left({n \over {\rm {e}}}\right)^{n}\left({n+1 \over {\rm {e}}}\right)^{n+1}}}$

$C_{n}\sim {\frac {e(4n^{2})^{n}}{{\sqrt {\pi (n+1)}}n^{n}(n+1)^{n+1}}}$

$C_{n}\sim {\frac {4^{n}}{\sqrt {\pi (n+1)}}}{\frac {(1+1/n)^{n}n^{n}}{(n+1)^{n+1}}}$

$C_{n}\sim {\frac {4^{n}}{\sqrt {\pi (n+1)}}}{\frac {(n+1)^{n}}{(n+1)^{n+1}}}$

$C_{n}\sim {\frac {4^{n}}{{\sqrt {\pi }}(n+1)^{3/2}}}$

$C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}$

Sources ?

La plupart des affirmations de l'article sont suffisamment peu évidentes (par exemple celle de l'unicité de la suite des nombres de Catalan pour que le déterminant des matrices de Hankel vaille 1 (et desquelles, d'abord? certainement pas de la matrice ((2 5) (5 14)) ) pour mériter une source précise, non?

Prolongement par continuité ?

L'article dit ceci :

« La série génératrice des nombres de Catalan est définie par$c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}$et en utilisant la relation de récurrence ci-dessus, on voit que$c(x)=1+xc(x)^{2}$et par conséquent$c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}$avec par prolongement par continuité : $c(0)=1.$ »

Tout d'abord, je ne sais pas si la notation ${\sqrt {}}$ s'applique à une série algébrique. J'écrirais plutôt

$c(x)={\frac {1-(1-4x)^{1/2}}{2x}}$.

Ensuite, il me semble inutile de faire intervenir un prolongement par continuité. Dans l'expression ci-dessus de c(x), le numérateur est une série de la forme

$2x+a_{2}x^{2}+...$,

donc le quotient est une série dont le terme constant est égal à 1. Je supprimerais donc les mots « avec par prolongement par continuité : $c(0)=1.$ » Marvoir (discuter) 24 décembre 2015 à 09:26 (CET)

La notation s'applique à la fonction (et est parfaitement traditionnelle) ; s'il est évident que la série vaut 1 en 0, l'expression donnée par la racine carrée vaut 0/0 (ou n'a pas de sens) et doit donc être prolongée par continuité.--Dfeldmann (discuter) 24 décembre 2015 à 10:15 (CET)

Pourquoi faire intervenir la notion de limite ? La « fonction génératrice » est une série formelle qui se définit de façon purement algébrique, sans qu'on doive se préoccuper de convergence. Et si on ne s'occupe pas d'une fonction à valeurs réelles, mais seulement d'une série, il me semble que la notation $c(x)={\frac {1-(1-4x)^{1/2}}{2x}}$ est préférable, puisqu'on ne peut pas attribuer un signe à une série formelle. Je rappelle que $(1-4x)^{1/2}$ est la série $\sum _{n}{1/2 \choose n}(-4x)^{n}$, avec une définition classique de $1/2 \choose n$. Marvoir (discuter) 24 décembre 2015 à 12:39 (CET)

Aïe, tu mélanges au moins trois choses (séries formelles, fonctions holomorphes, et fonctions algébriques réelles). Voici une présentation plus rigoureuse : Posons $c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}$, dont le rayon de convergence est 1/4, et f la fonction réelle $f(x)={\frac {1-(1-4x)^{1/2}}{2x}}$, qui est (pour x non nul) une des solutions de l'équation algébrique $f=1+xf^{2}$ (dans ce contexte réel, le symbole racine carré et la puissance 1/2 sont strictement synonymes). Le domaine de définition de f est $]-\infty ,0[\cup ]0,1/4]$. Sur $[-1/4,1/4[-\{0\}$, $c(x)=f(x)$. En 0, $c(0)=1$, mais $f(0)$ n'est pas définie, et pour que $f(0)=c(0)=1$, il faut prolonger f par continuité. Voilà, j'espère que c'est plus clair (et plus rigoureux) ainsi. Accessoirement, les valeurs de c(x) pour $|x|>1/4$ relèvent d'une autre sorte de prolongement, le prolongement analytique ; s'il est encore acceptable de dire (au sens d'Euler, mettons) que $c(-1)=\sum _{n=0}^{\infty }(-1)^{n}C_{n}=(1-{\sqrt {5}})/2$ (voir l'article série divergente), il semble nettement plus douteux d'écrire, même formellement, $c(1)=\sum _{n=0}^{\infty }C_{n}=e^{-i\pi /3}$...--Dfeldmann (discuter) 24 décembre 2015 à 20:09 (CET)

Non, je ne mélange rien du tout, c'est vous qui introduisez la notion de convergence où elle n'a que faire. Voici ma démonstration : une fois qu'on a trouvé (voir ci-dessus)

$c(x)=1+xc(x)^{2}$,

autrement dit

$xc(x)^{2}-c(x)+1=0,$

on peut multiplier par 4x, d'où

$(2xc(x)-1)^{2}=1-4x,$

donc

$2xc(x)-1=\pm (1-4x)^{1/2},$

$2xc(x)=1\pm (1-4x)^{1/2},$

où $(1-4x)^{1/2}$ est la série définie comme je l'ai dit dans mon précédent message.

La solution avec le signe + est impossible, parce qu'alors le second membre n'est pas divisible par x dans l'anneau des « séries entières » (la terminologie varie, mais on se comprend). Donc

$2xc(x)=1-(1-4x)^{1/2},$

d'où

$c(x)=(1-(1-4x)^{1/2})/2x.$

Et il n'y a rien d'autre à ajouter : toute personne qui sait calculer le quotient par x d'une série divisible par x trouvera que le terme constant de c(x) est égal à 1. Marvoir (discuter) 24 décembre 2015 à 20:43 (CET)

Bon, je vois que ça va se compliquer. Vous avez, je l'admet, formellement raison, si ce n'est que vos notations sont à tout le moins non standard (avez-vous une référence pour écrire votre dernière ligne?). Parce que, du coup, vous obtenez inévitablement (par substitution à x de la série formelle 1=1+0x+0x^2) l'étrange résultat $c(1)=\sum _{n=0}^{\infty }C_{n}=(1-(-3)^{1/2})/2=e^{-i\pi /3}$, et vous résolvez au passage de passionnantes questions sur les points de ramification d'une fonction holomorphe. Autrement dit, je crains qu'il soit au contraire plus prudent de ne mentionner le point de vue formel que pour mémoire, et de parler, justement, de questions de convergence au niveau, somme toute élémentaire, où se place cet article (et, de fait, la référence standard sur ces questions qu'est le livre de Flageolet et Sedgewick signale également ce problème)--Dfeldmann (discuter) 24 décembre 2015 à 21:04 (CET)

Voici une référence pour la notation que j'ai utilisée dans la dernière ligne de mon précédent message : Bourbaki, Algèbre, ch. I, 1970, § 7, exerc. 5, c, p. I.144. Je ne trouve pas qu'il soit « plus prudent de ne mentionner le point de vue formel que pour mémoire » et qu'il soit plus élémentaire de parler de convergence. L'article Série génératrice, auquel l'article Nombre de Catalan renvoie, traite les séries de façon algébrique, sans s'occuper de convergence, et pour moi c'est la meilleure façon de faire : je ne vois pas comment un lecteur qui serait incapable de dégager la notion de série formelle des contingences de convergence pourrait comprendre le rôle joué par la série génératrice. (P.S. J'éteins mon PC jusqu'à demain.) Marvoir (discuter) 24 décembre 2015 à 21:34 (CET)

Ok, finalement, après une lecture plus soignée, les liens donnés par l'article justifient tout à fait votre point de vue, que je m'excuse d'avoir mis en doute. Un lecteur aussi inattentif que je l'ai été risque cependant d'être surpris par ces questions de convergence ; peut-être pourrait-on en effet supprimer cette histoire de prolongement, mais rappeler en note ce qui se passe pour la série entière correspondante.--Dfeldmann (discuter) 25 décembre 2015 à 01:09 (CET)

Voici une référence récente. F. Bories-Longuet et J. Ramírez-Alfonsín, Graphes et combinatoire, Ellipses, 2015, p. 239, commencent le chapitre 11, Fonctions génératrices, par une introduction, puis, dans une section 11.2, p. 240, « développent la théorie des séries formelles ». Dans l'introduction, p. 239, ils disent : « ici, on ne se posera aucun problème de convergence ». Je suis évidemment d'accord avec vous pour supprimer ce qui concerne le prolongement par continuité. Quant à parler de la fonction de R dans R ou de C dans C correspondant à la série formelle, cela demande de prouver que le rayon de convergence de la série n'est pas nul. On peut évidemment le faire en utilisant la valeur asymptotique des nombres de Catalan donnée dans l'article, mais je me demande si cela vaut vraiment la peine. « Cette fonction n'apporte rien à la connaissance des nombres de Catalan (en tout cas dans le cadre de l'article). » Marvoir (discuter) 25 décembre 2015 à 08:13 (CET)

Cependant, c'est cette approche qui est proposée par (en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2008 (ISBN 0-521-89806-4, lire en ligne) (p.7), certes pour illustrer la méthode, inutile dans ce cas au vu de la formule de Stirling. Bon, en fin de compte, tout cela a bien peu d'importance...--Dfeldmann (discuter) 25 décembre 2015 à 08:57 (CET)

J'ai bien dit : « Cette fonction n'apporte rien à la connaissance des nombres de Catalan (en tout cas dans le cadre de l'article). » Flajolet et Sedgewick s'intéressent à la combinatoire analytique, mais cela sort du cadre du présent article. On n'a pas besoin de combinatoire analytique pour trouver le terme constant de la série c(x), on n'a même pas besoin de savoir que le rayon de convergence de cette série est non nul. Le comportement asymptotique des coefficients est une autre question. Si la combinatoire analytique permet de trouver une expression asymptotique des nombres de Catalan plus précise que celle qui est donnée dans l'article (pour ma part, je suis ignorant en la matière), alors la fonction analytique associée à la série devient intéressante, mais faire intervenir cette fonction analytique pour déterminer un coefficient qui se calcule trivialement me semble être un coup de canon tiré pour tuer une mouche. Pour moi, c'est une tache dans l'article. Marvoir (discuter) 25 décembre 2015 à 09:46 (CET)

Pour essayer de se mettre d'accord, je propose d'écrire ceci dans l'article :

$c(x)=1+xc(x)^{2}$,

autrement dit

$xc(x)^{2}-c(x)+1=0,$

d'où (règle des racines du trinôme du second degré, valable dans tout corps commutatif de caractéristique distincte de 2)

$(1)\qquad c(x)={\frac {1\pm (1-4x)^{1/2}}{2x}},$

la série $(1-4x)^{1/2}$ étant définie comme égale à la série

$\sum _{n}{1/2 \choose n}(-4x)^{n}$, avec

${1/2 \choose n}={\frac {{\frac {1}{2}}({\frac {1}{2}}-1)\ldots ({\frac {1}{2}}-n+1)}{n!}}$.

(La série $(1-4x)^{1/2}$ a pour carré la série $\ 1-4x$, ce qui légitime le raisonnement qui précède.) Le numérateur du second membre de (1) doit être une série divisible par x, donc seul le signe $\ -$ convient dans $\pm ,$ donc

$\qquad c(x)={\frac {1-(1-4x)^{1/2}}{2x}},$

En explicitant les coefficients de la série formant le second membre, on trouve la valeur $C_{n}={\frac {1}{n+1}}{2n \choose n}$, déjà indiquée plus haut.

Je n'ai pas d'objection à ce qu'on mentionne la fonction analytique associée à la série, mais pour ma part, je suis incapable de dire quelque chose d'intéressant à son sujet. Et je continue à penser que le prolongement par continuité est sans intérêt. Considérer la série formelle

$(1-4x)^{1/2}=\sum _{n}{1/2 \choose n}(-4x)^{n}$

fournit presque instantanément une forme explicite de tous les nombres de Catalan. Dans le cadre actuel de l'article, la fonction analytique n'apporte donc pas grand-chose. Marvoir (discuter) 25 décembre 2015 à 11:40 (CET)

Oui,mais je pense qu'il n'y a pas besoin d'en faire tant... je propose tout simplement de supprimer cette histoire de prolongement, et d'écrire en note quelque chose comme " cette écriture est parfaitement rigoureuse dans le cadre des séries formelles ; si on interprète c(x) comme une série entière, on démontre que son rayon de convergence est 1/4 , et que sur l'intervalle réel [-1/4,1/4], on a c(x)=..., en prolongeant le membre de droite en 0 par la valeur 1" . Si ça te convient, je modifie l'article en ce sens.--Dfeldmann (discuter) 25 décembre 2015 à 13:17 (CET)

N'est-il pas dommage de manquer l'occasion de montrer que la série (formelle) génératrice permet d'expliciter les nombres de Catalan ? C'est un des principaux usages de la série génératrice : à partir d'une définition par récurrence, trouver une expression « explicite ». Marvoir (discuter) 25 décembre 2015 à 14:01 (CET)

Oui, c'est une bonne idée ; je le rajoute.--Dfeldmann (discuter) 25 décembre 2015 à 14:14 (CET)

Merci ! Marvoir (discuter) 25 décembre 2015 à 14:23 (CET)

nombre de catalan formule

bonjour, la formule pour le nombres de catalan est fausse non? Ici il s'agit de la formule pour C_(n+1) Flaubest (discuter) 7 août 2022 à 02:26 (CEST)

Bonjour. L'expression actuelle est correcte. Cf le lien sur l'OEIS. Adam Bross (discuter) 7 août 2022 à 13:59 (CEST)

Arbre **planaire** ?

Étant donné qu'un arbre est un graphe acyclique connexe (planaire) et qu'ici il n'y a pas de confusion possible avec un autre type d'arbre d'une autre discipline, pourquoi parler d'arbre planaire enraciné au lieu de parler d'arbre enraciné ? 2A02:8428:14D2:1F01:8405:B95:2050:4CA4 (discuter) 4 février 2023 à 17:11 (CET)

Nombre de Fuss Catalan?

Il y a une page nombre de Fuss Catalan en anglais mais pas en Français. Il semble que notre ami Karol Penson est écrit sur ces nombres. Pour les nombres de Catalan il y a un joli graphe régulier, le omega demi boudin, qui donne pour le nombre de chemin de longueur n allant de l’état 0 à l’état 0, le nième nombre de Catalan. Pierre Joseph Simonnet (discuter) 17 mars 2023 à 08:24 (CET)

Pourquoi préciser que la loi est non associative ?

Dans l'interprétation en nombre de parenthésages, pourquoi préciser que la loi est non associative ? Car même si elle est non associative, il se peut que (ab)c soit égal à a(bc) pour certains (a,b,c). Si on veut que tous les résultats des parenthésages soient distincts il faudrait préciser que la loi est "anti-associative" à savoir que (ab)c n'est jamais égal à à a(bc) non ? En fait c'est le nombre d'écritures qui est important, pas le nombre de résultats de ces écritures. Robert FERREOL (discuter) 29 mars 2023 à 08:07 (CEST)