nombre de Catalan
COMBINATOIRE
Notion de combinatoire.
Les nombres de Catalan forment une suite d’entiers naturels.
Cette suite avait été découverte par Euler dans la recherche du nombre de façons de découper un polygone en triangles par des diagonales ne se coupant pas.
Catalan la retrouva dans le dénombrement des parenthésages d’un produit de n nombres (sans changer l’ordre des facteurs et en les regroupant 2 par 2).
Le n-ième nombre de Catalan, noté Cn, est défini en fonction du précédent par :
Cn = (2 (2n-3) / n) Cn-1.
Une écriture explicite utilisant les coefficients binômiaux est :
Cn = (1 / (n+1)) C2nn = (2n) ! / ((n+1) ! n ! ).
Les premiers nombres de Catalan sont :
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862 …
On peut aussi les trouver à parttir du triangle de Pascal de la façon suivante : on prend le terme du milieu de chacune des lignes qui contiennent un nombre impair de termes. Et on divise ces nombres respectivement par 1, 2, 3, 4, 5, .
Les nombres de Catalan sont des entiers naturels.
En dehors des problèmes cités plus haut, les nombres de Catalan interviennent dans de nombreux problèmes de combinatoire tels que : Cn est égal au nombre de mots de Dyck de longueur 2n, Cn est le nombre d’arbres binaires entiers à n+1 feuilles, Cn est le nombre de chemins monotones le long des arêtes d’une grille à n × n carrés, qui restent sous (ou au niveau de) la diagonale.