nombre de Catalan

Prenons quatre facteurs écrits dans un ordre fixé : a, b, c et d. On peut placer les parenthèses de cinq façons pour indiquer quels produits effectuer d’abord, sans déplacer aucun facteur.

Ce total, 5, est un nombre de Catalan. La même suite réapparaît quand on compte des objets très différents soumis à une règle analogue : construire par étapes tout en respectant un ordre et sans créer de croisement interdit.

Les nombres de Catalan sont des entiers qui dénombrent plusieurs familles d’objets combinatoires. Avec la convention usuelle, le nombre d’indice n, noté C_n, commence à l’indice 0 : C₀ = 1, puis 1, 2, 5, 14, 42, 132, 429, 1430 et 4862. Pour tout entier n supérieur ou égal à 0, il vaut :

Pour n supérieur ou égal à 1, la récurrence compatible avec cette convention est $C_n=\frac{2(2n-1)}{n+1}{C}_{n-1}C\_n=\backslash frac\{2(2n-1)\}\{n+1\}C\_\{n-1\}$. Ainsi, C_n compte les mots de Dyck de longueur 2n, les arbres binaires complets à n + 1 feuilles et les chemins monotones d’une grille n × n qui ne passent pas au-dessus de la diagonale. Il compte aussi les parenthésages binaires de n + 1 facteurs gardés dans leur ordre et les triangulations d’un polygone convexe à n + 2 sommets. Euler a rencontré la suite avec les triangulations ; Catalan l’a retrouvée avec les parenthésages. Enfin, le triangle de Pascal donne C_n en divisant son coefficient central de rang 2n par n + 1.

On veut compter les parenthésages binaires du produit a × b × c × d. Les quatre facteurs sont distincts seulement pour rendre leur ordre visible ; cet ordre ne change jamais. Chaque opération regroupe exactement deux sous-produits.

1. On sépare le produit après a. Cela donne a × (b × (c × d)) et a × ((b × c) × d).
2. On le sépare entre b et c. On obtient (a × b) × (c × d).
3. On le sépare avant d. Cela donne (a × (b × c)) × d et ((a × b) × c) × d.
4. Les trois cas sont disjoints, car la dernière multiplication ne coupe pas le produit au même endroit. Leur total est 2 + 1 + 2 = 5.

Quatre facteurs correspondent à l’indice n = 3, donc le résultat est C₃ = 5. Pour contrôler le calcul, la récurrence part de C₂ = 2 et donne $C_3=\frac{2(2\times 3-1)}{3+1}\times 2=5C\_3=\backslash frac\{2(2\backslash times3-1)\}\{3+1\}\backslash times2=5$. La figure rassemble les cinq structures de parenthèses sans modifier l’ordre a, b, c, d.

Pour un produit dont les facteurs restent dans le même ordre, C_n remplace une énumération manuelle des parenthésages binaires de n + 1 facteurs. Si l’ordre peut changer, ce nombre ne suffit plus : il faut compter aussi les permutations autorisées.

Pour un chemin monotone dans une grille carrée, C_n s’emploie lorsque le trajet reste du même côté de la diagonale. Sans cette contrainte, le coefficient binomial central compte tous les chemins monotones, y compris ceux qui franchissent la diagonale.

Pour une triangulation, on vérifie que le polygone est convexe et que les diagonales ne se coupent pas à l’intérieur. Si des croisements sont permis ou si le polygone n’est pas convexe, le modèle de Catalan ne décrit plus directement les configurations admissibles.

Coefficient binomial central. Le coefficient $\left(\genfrac{}{}{0px}{}{2n}{n}\right)\backslash binom\{2n\}\{n\}$ compte tous les chemins monotones entre deux coins opposés d’une grille n × n. Le nombre de Catalan impose en plus de rester d’un côté de la diagonale et divise ce coefficient par n + 1. Pour n = 4, les deux résultats sont 70 et 14.

Valeur d’un produit. Les nombres de Catalan comptent les structures de parenthèses, pas les résultats numériques du produit. Avec des nombres et une multiplication associative, les cinq parenthésages de quatre facteurs ont la même valeur, mais restent cinq regroupements distincts.

Décalage d’indice. La convention C₀ = 1 associe C_n à n + 1 facteurs. Si l’on appelle C₁, C₂, … les termes successifs 1, 1, 2, …, la récurrence s’écrit alors $C_n=\frac{2(2n-3)}{n}{C}_{n-1}C\_n=\backslash frac\{2(2n-3)\}\{n\}C\_\{n-1\}$. Il faut donc vérifier l’indice avant d’appliquer une formule.

Cas vide. À l’indice n = 0, la valeur C₀ = 1 ne signifie pas qu’un objet visible a été construit. Elle compte l’unique structure vide, convention nécessaire pour amorcer proprement les formules et les récurrences.

Contraintes oubliées. Le comptage de Catalan dépend de règles précises : ordre fixé pour les facteurs, regroupements binaires, diagonales non sécantes, ou chemin restant du bon côté de la diagonale. Dès qu’une règle disparaît, le symptôme est un total différent ; il faut reformuler l’ensemble compté avant de choisir la formule.

Le triangle de Pascal permet de retrouver les nombres de Catalan à partir des coefficients centraux et d’observer leur lien avec les coefficients binomiaux.

Le mot de Dyck donne une incarnation précise de C_n sous la forme d’un mot équilibré de longueur 2n.

L’analyse combinatoire replace ces dénombrements dans les méthodes générales qui organisent et comptent des configurations finies.