Nombre de Catalan
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (En mathématiques un coefficient est un facteur multiplicatif qui dépend d'un certain objet, comme une variable (par exemple, les coefficients d'un polynôme), un espace vectoriel, une fonction de base et ainsi de suite....) 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 (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.)

  • Cn est égal au nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de mots de Dyck de longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou...) 2n. Un mot de Dyck est un mot formé de n lettres X et de n lettres Y, tel qu'aucun abrègement du mot à la finale (obtenu en supprimant les dernières lettres à partir d'un rang ( Mathématiques En algèbre linéaire, le rang d'une famille de vecteurs est la dimension du sous-espace vectoriel engendré par cette famille. Le théorème du rang lie le rang et la dimension du noyau d'une application...) quelconque) ne contienne plus de Y que de X. Autrement dit, lorsque nous parcourons un mot de Dyck de gauche à droite, le nombre de X rencontrés est toujours supérieur ou égal au nombre de Y. Par exemple, les mots de Dyck de la longueur 6 sont:
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 (En algèbre linéaire, la diagonale principale d'une matrice est la diagonale qui descend du coin en haut à gauche jusqu'au coin en bas à droite. Par exemple, la matrice carré d'ordre 2, qui suit a des 1 sur sa diagonale...). 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 (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...) Cn.
  • Cn est également le nombre de façons différentes de placer des parenthèses autour (Autour est le nom que la nomenclature aviaire en langue française (mise à jour) donne à 31 espèces d'oiseaux qui, soit appartiennent au genre Accipiter,...) de n + l facteurs. Pour n = 3 par exemple, nous obtenons 5 façons différentes de placer des parenthèses autour de 4 facteurs: a(b(cd)), a((bc)d), (ab)(cd), (a(bc))d, ((ab)c)d. De telles expressions peuvent être naturellement représentées par des arbres binaires complets ordonnés, et Cn donne également le nombre de ces arbres à n + 1 feuilles.
Triangulations
Triangulations
  • Cn est également égal au nombre de différentes façons dont un polygone (En géométrie euclidienne, un polygone (du grec polus, nombreux, et gônia, angle) est une figure géométrique plane, formée d'une suite cyclique de segments consécutifs et délimitant une portion...) à n + 2 côtés peut être partagé en triangles en reliant ses sommets par des segments de droite.
  • Cn est également le nombre de partitions non croisées de l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) {1, ..., n }. A fortiori, Cn n'excède jamais le nème nombre de Bell (Les nombres de Bell, qui portent le nom de Eric Temple Bell, se rencontrent souvent en combinatoire. Ces nombres forment une suite d'entiers qui commence...).

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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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 (En mathématiques, la fonction génératrice de la suite (an) est la série formelle définie par) 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 première publication sur ces nombres est due à Segner et la suite porte alors le nom de Nombre de Segner. Eugène Charles Catalan fit le lien avec le nombre d'expressions " parenthésées " et le nom de Catalan remplaça celui de Segner. L'astuce de comptage des mots de Dyck fut trouvée par Désiré André en 1887.

Page générée en 0.139 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique