Nombres de Catalan (agreg interne)

permaths · March 2020

Bonjour à tous,
je travaille sur les nombres de Catalan et sur la démo faite dans le Kieffer.

Je ne comprends pas bien la conclusion. En montrant que deux séries entières vérifient la même équation fonctionnelle, on ne peut pas montrer que les deux séries entières sont égales ? Il faut montrer que les deux séries vérifient une même relation de récurrence ?
Si quelqu'un a ce livre sous les yeux, c'est page 648. Comment démontrer que la suite b_n vérifie l'égalité ?

Merci pour votre aide.

Chaurien · March 2020

Le Kieffer ?

Math Coss · March 2020

Je n'ai pas le livre sous les yeux mais pour l'équation fonctionnelle $f(X)^2=1$, il y a deux séries entières solutions.

permaths · March 2020

oui, c'est un livre de leçons pour l'agreg interne.
Probablement, que l'on trouve cette démo ailleurs, si quelqu'un a une autre référence, ça m'intéresse aussi.

Chaurien · March 2020

Louis Comtet, Analyse Combinatoire, Tome premier, PUF 1970, p. 66.
Louis Comtet, Advanced Combinatorics, D. Reidel, 1974, p. 53.
Les nombres de Catalan sont certainement les nombres qui ont le plus d'interprétations combinatoires et il y a toute une littérature à leur sujet.
Bonne soirée.
Fr. Ch.

aléa · March 2020

On peut le trouver dans Graphes et combinatoire - Cours avec 210 exercices corrigés
de Francette Bories-Longuet et Jorge Alfonsin Ramirez, très bon livre.

Eric · March 2020

Au bout de six messages, je ne sais toujours pas de quoi on parle ...
Tu parles d'une démonstration, mais tu ne dis rien de la proposition à démontrer. Quelle proposition s'agit-il ?

permaths · March 2020

voici en pj la démo du livre
mon problème est à la fin, quand on dit que (bn) satisfait la même relation de récurrence que (an), pourquoi bn=somme.... ? 98174

Eric · March 2020

Quand je vois ça, je me dis qu'il s'agit d'une histoire de fonction génératrice et immédiatement je pense à Generatingfunctionology. Du coup, je vais y voir (la deuxième édition est disponible légalement en ligne https://www.math.upenn.edu/~wilf/gfologyLinked2.pdf) et une recherche sur Catalan me conduit aux pages 43 et 44 ... et là, je me dis que Mr Wilf savait vachement bien rédiger.

permaths · March 2020

je comprends pour les an mais toujours pas pour les bn

Petit mathématicien · March 2020

il me semble qu'il te suffit d'écrire $f(x)=\sum b_n x^n$ et comparer avec le 2) tout simplement non ?

Romanesco · March 2020

Les nombres de Catalan sont évoqués aussi dans le tome 4 d'analyse de Monier (3è édition). Je ne peux pas en dire plus je n'ai pas regardé l'exercice :-(

Mieses · March 2020

Il y a un problème dans sa démonstration car il tient pour acquis que le rayon de convergence $R$ de la série $\sum a_{n}x^{n}$ est non nul ce qui n'a rien d'évident. Pour contourner la difficulté on peut raisonner avec les séries formelles mais elles ne sont pas au programme de l'interne je crois.

permaths · March 2020

Ok
merci pour votre aide, ça avance ;-)

Eric · March 2020

C'est une identité combinatoire, donc pourquoi pas un argument combinatoire, par exemple avec le principe de symétrie de André (qui n'est pas de André) https://fr.wikipedia.org/wiki/Problème_du_scrutin

Tu trouveras le détail par exemple dans A path to combinatorics de Andreescu et Feng (Birkhäuser), p. 111-112 (pas trop difficile à visualiser sur le net).

J'ai l'impression que ton bouquin supposé tout faire, du genre tout-en-rien, ne va pas au bout des choses.

permaths · March 2020

Alors, ce que je viens de comprendre, c'est que ce que je pensais qu'il fallait démontrer était en fait la conclusion...
Les 2 séries entières vérifient la même équation fonctionnelle donc an=bn (et donc bn vérifie de ce fait la relation de rec...)
Le seul hic maintenant, c'est de montrer pourquoi la série entière avec an a un RDC non nul.

Math Coss · March 2020

Eric a écrit:

principe de symétrie de André (qui n'est pas de André)

Ça, c'est sûr ! Même si éventuellement, ça pourrait/aurait pu être « d'André ».

Eric · March 2020

https://www.e-periodica.ch/digbib/view?pid=ens-001:1923:23#173 p.185 et p.187 (avec, bien sûr, référence à André ... et donc ça aurait pu être ...)

jandri · March 2020

Je n'ai pas la même définition du nombre de parenthésages que celle qui est proposée dans le livre photographié.

Pour moi $c_n$ est le nombre de façons de placer correctement $n$ paires de parenthèses. Par exemple pour $n=3$ il y a 5 façons :
()()(), (())(), ()(()), (()()) et ((())).

Comme il y a au plus deux possibilités pour chaque parenthèse, il est immédiat que $c_n\leq 2^{2n}$. Cela entraîne que le rayon de convergence de $\sum c_nx^n$ est au moins égal à $\dfrac14$.

C'est la même chose pour le $a_n$ du livre.

permaths · March 2020

an = nombre de parenthèsages possibles sur X1...Xn
comment je déduis que an <= 2^(2n) ?

gerard0 · March 2020

Il y a 2n places possibles pour les 2n parenthèses, que le placement soit correct ou incorrect. Et deux sortes de parenthèses possibles.
Bien évidemment, c'est une majoration grossière !

Cordialement.

rimf84 · March 2020

Bonjour,
J'arrive 10 jours après la bataille mais si certains passent par là et cherchent une référence...
En bossant les probabilités dans le nouveau livre de Laurent Le Floch et Frédéric Testard, j'ai vu que cela est traité en exercice p 481.
Cordialement

kolotoko · April 2020

Bonjour,
les nombres de Catalan C_n sont les nombres 1,1,2,5,14,42,132,429,...pour n = 0,1,2,3,4,5,6,7,...respectivement.

Pour en savoir plus, consulter : Catalan Numbers with Applications de Thomas Koshy chez Oxford University Press , 422 pages.
Bien cordialement.
kolotoko