Page d'accueil encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Nombre de Catalan

Les nombres de Catalan sont des entiers naturels qui se rencontrent souvent dans les problèmes de combinatoire. Ils forment une suite dont le terme d'indice n, appelé nème nombre de Catalan est défini par

C_n=\frac{1}{n+1}C_{2n}^n

(voir coefficient binomial). Les premiers nombres de Catalan pour n=0, 1, 2, 3, ... sont

1, 1, 2, 5, 14, 42, 132, 429, 1430, ...

Tous les nombres de Catalan sont des entiers naturels parce qu'ils peuvent s'écrire sous la forme:

pour n≥1, C_n=C_{2n}^n-C_{2n}^{n-1}

Applications en combinatoire

XXXYYY, XYXXYY, XYXYXY, XXYYXY, XXYXYY.
En l'occurrence, C3= 5.
Assimilant X à une parenthèse ouvrante et Y à une parenthèse fermante, un mot de Dyck de longueur 2n peut être vu comme une expression formée de n paires de parenthèses correctement assemblées: ((())), ()(()), ()()(), (())(), (()()). Les mots de Dyck peuvent être naturellement représentés comme des chemins dans un quadrillage de n +1 points par n+1 points, reliant certains points par les traits verticaux et horizontaux. Ces chemins commencent dans le coin inférieur gauche, et se terminent dans le coin supérieur droit, en allant toujours vers le haut ou vers la droite, mais ne passant jamais au-dessus de la diagonale principale. X représente alors un « déplacement vers la droite » et Y représente un « déplacement vers le haut ».
Nous pouvons compter les mots de Dyck avec l'astuce suivante due à D. André (principe de symétrie): intéressons nous aux mots contenant n X et n Y qui ne sont pas des mots de Dyck. Dans de tels mots, déterminons le premier Y qui brise la condition de Dyck, puis modifions toutes les lettres qui suivent ce Y, en échangeant X avec Y et vice versa. Nous obtenons un mot avec n + 1 Y et n- 1 X, et en fait tous les mots comportant n + 1 Y et n- 1 X peuvent être obtenus par ce moyen et de manière unique. Le nombre de ces mots est le nombre de façons de placer les n-1 X dans 2n emplacements et est égal à
C_{2n}^{n-1}
ce qui donne le nombre de mots qui ne sont pas de Dyck; le nombre de mots de Dyck s'en déduit et est égal à
C_{2n}^n-C_{2n}^{n-1}
qui est le nème nombre de Catalan Cn.

Relation de récurrence et comportement asymptotique

Les nombres de Catalan satisfont la relation de récurrence

C_0 = 1 \qquad \mbox{et pour}\quad n\ge 1 \qquad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}
Ceci vient du fait que tout mot w de Dyck de longueur supérieure à 2 peut s'écrire de manière unique sous la forme
w = Xw1Yw2
avec des mots de Dyck (éventuellement vides) w1 et w2.

La fonction 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 nous voyons que

c(x)=1+xc(x)^2\,

et par conséquent

c(x) = \frac{1-\sqrt{1-4x}}{2x}

Asymptotiquement, les nombres de Catalan se comportent comme

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

Histoire

La suite de Catalan fut décrite pour la première fois au XVIIIe siècle par Leonhard Euler, qui s'était intéressé au nombre de différentes façons de partager un polygone en triangles. La suite porte le nom d'Eugène Charles Catalan, qui fit le lien avec le nombre d'expressions « parenthésées ». L'astuce de comptage des mots de Dyck fut trouvée par D. André en 1887.


This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the GNU Free Documentation License Page HistoryOriginal ArticleWikipedia