Les nombres de Catalan

Cidrolin

Dans le cadre de Mathematic Park, j'ai assisté à un très bel exposé de Viviane Pons sur les nombres de Catalan. Elle dénombre les triangulations des polygones, les chemins de Dyck, et les arbres binaires... et termine par la formule de $C_n$.
Pour $n$ fixé, y a-t-il un moyen d'associer une triangulation à un chemin de Dyck ? Je m'en veux de ne pas lui avoir posé la question sur l'existence de cette bijection (naturelle), n'ayant pensé à cela qu'en regagnant mes pénates.
Amicalement

Math Coss

Oui, voir ce texte. On part d'un $n+1$-gone inscrit dans un cercle (gris). On choisit un côté que l'on note $*$. Puis, pour une triangulation donnée (en noir), on construit un arbre (en bleu) : c'est essentiellement le graphe dual de la triangulation. Partant de là, on parcourt l'arbre en partant de sa racine $*$ en suivant un parcours « main droite » et on construit un chemin de Dick comme ça : si on s'éloigne de la racine, on fait un pas vers le haut ; si on se rapproche, un pas vers le bas.

Dans l'exemple, on part vers la gauche et construit le chemin de Dick suivant : on s'éloigne de deux pas jusqu'à atteindre la feuille en bas à gauche, on se rapproche d'un pas, on s'éloigne de trois pas pour atteindre la feuille en haut à gauche, etc.

     /\/\
    /    \/\
 /\/        \
/            \

Aparté : les premières recherches m'ont conduit sur le livre Large random matrices, ce qui donne l'occasion de dire que son auteur Alice Guionnet vient d'être élue membre de l'Académie des sciences.

Chaurien

Jusqu'à présent, on parlait de trajets sous- (ou sur-) diagonaux, énumérés grâce aux idées de Désiré André, toutes choses bien connues.
Voici qu'apparaît un « Dyck » (attention, pas un « Dick», qui peut se prêter à des plaisanteries). Qui est ce « Dyck » dont l'irruption est des plus étranges dans un problème déjà ancien ?
Pour la bijection souhaitée, la notice Wikipedia répond
https://fr.wikipedia.org/wiki/Nombre_de_Catalan
Tout ça est bien mystérieux...
Fr. Ch.

Cidrolin

@Math Coss C'est ce que je cherchais. Comme on dit en oudmourte$ ^*$ : "tau".

@Chaurien, https://en.wikipedia.org/wiki/Walther_von_Dyck


$ ^*$ voir http://www.freelang.com/expressions/merci.php

Math Coss

Tiens, c'est amusant, l'excellente Alice Guionnet écrit “Dick path” dans son livre. (Je ne veux pas faire semblant de l'avoir lu, je n'ai feuilleté que les premières pages qui donnent la correspondance entre arbres binaires planaires enracinés et chemins de D.ck ci-dessus.)

Eric

Et pas si sûr que ce soit les idées de D. André ...

La publication de André est disponible sur Gallica :
http://gallica.bnf.fr/ark:/12148/bpt6k3061j/f436.image

Il répondait à une question de Bertrand :
http://gallica.bnf.fr/ark:/12148/bpt6k3061j/f369.image

En fichiers joints, un historique du problème du scrutin de Bertrand.

kolotoko

Bonjour,

on peut consulter l'article sur Walther von Dyck sur Wikipédia et le livre de Thomas Koshy :Catalan Numbers with Applications (Oxford University Press ).

Les nombres de Catalan sont référencés A000108 sur O.E.I.S.

Bien cordialement.

kolotoko

GaBuZoMeu

J'avais rapporté dans le temps, dans ce message, ce qui me semble la plus belle façon d'établir la formule $\dfrac{1}{n+1}\pmatrix{2n\\ n}$. La plus belle, parce qu'elle correspond parfaitement à cette formule : on fait un choix de $n$points parmi $2n$ points disposés sur un cercle, ce choix détermine un système de $n$ cordes non sécantes du cercle plus une des $n+1$ régions du disque délimitées par ces $n$ cordes. Or, ce qu'on compte avec les nombres de Catalan, c'est justement le nombre de systèmes de $n$ cordes non sécantes.
Le dessin du message que j'ai mis a lien a disparu. Le voici :

[J'ai rétabli le dessin dans le lien cité. Merci d'Alerter un modérateur sur de tels messages. :-) AD]
Merci AD, je n'osais pas déranger un modérateur pour si peu. Comme j'ai allongé mon pseudo, je n'avais plus les identifiants pour le faire moi-même.

Cidrolin

Comme on dit en cherokee : wado
http://www.freelang.com/expressions/merci.php

samok

Chacun ses hobby(s) sieur Chaurien.

S

Chaurien

Ii y a longtemps que je m'intéresse aux nombres de Catalan, qui sont certainement la suite de nombres qui a le plus d'interprétations combinatoires.
J'apprends à leur sujet quelque chose de nouveau et j'en suis fort aise. Ma principale référence est bien sûr le Comtet, qui ne mentionne pas Von Dyck. J'ai regardé çà et là et j'ai pris conscience de l'importance de ce mathématicien que je ne connaissais pas, notamment dans l'histoire de l'émergence du concept de groupe.
http://www-groups.dcs.st-and.ac.uk/history/Biographies/Von_Dyck.html
Maintenant je trouve choquant que notre charmante académicienne ne prenne pas la peine d'orthographier correctement le nom de ce mathématicien et j'espère que personne ne lui fera à cette occasion des plaisanteries déplacées.
Bonne journée.
Fr. Ch.

Chaurien

J'ajoute que je ne comprends pas l'interpellation de Samok.

samok

les zobis, tu comprends mieux là ?

S

Chaurien

Toujours ce problème de liaison comme avec les zaricots. Franchement je n'avais pas compris.

Shah d'Ock

Chaurien a écrit:

et j'espère que personne ne lui fera à cette occasion des plaisanteries déplacées.

On aurait tort de se priver. Vive la liberté, et vive la rigolade!

Chaurien

Shah d'Ock, tu me cherches, mais tu ne me trouveras pas. Il y a un bon usage de la liberté...

Fin de partie

Le prénom de Dyck c'est Moby? C'est bon je sors....X:-(

Rescassol

Bonsoir,

Non, c'est PhilippeK.

Cordialement,

Rescassol

Rescassol

Bonsoir,

D'ailleurs, saviez vous que les beaux parents de Philip K.Dick étaient originaires de Nemours ?

C'est parce que la belle de K.Dick a des vieux de nemours.

Bon, je sors aussi ........

Cordialement,

Rescassol