🔢 Nombres de Catalan

Un (n+2)-gone convexe peut être divisé en triangles en traçant n–1 diagonales non croisées ; le nombre de façons de le faire est Cₙ. Pour un quadrilatère (n = 2) : deux triangulations. Pour un pentagone (n = 3) : cinq triangulations. La bijection vers les chaînes de parenthèses fonctionne en fixant une arête du polygone comme « racine » et en remarquant que le triangle appuyé sur cette arête divise le reste du polygone en deux polygones plus petits, reflétant la récurrence de Catalan Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ Cₙ₋₁₋ᵢ. Les triangulations apparaissent en géométrie computationnelle (triangulation optimale de polygones, triangulation de Delaunay), en méthodes numériques (maillage par éléments finis), et en conception de compilateurs (arbres syntaxiques).

Un diagramme de cordes non croisées est constitué de 2n points sur un cercle reliés par n cordes ne se croisant pas. Les C₃ = 5 façons de relier 6 points par 3 cordes non croisées sont exactement les cinq objets de Catalan pour n = 3. Ces diagrammes apparaissent dans la prédiction de structure secondaire de l'ARN (les paires de bases sont des cordes non croisées sur la séquence), la théorie des nœuds (algèbres de Temperley–Lieb), et les probabilités libres (les partitions non croisées définissent les cumulants libres des distributions de probabilité). Le nombre de partitions non croisées de {1, …, n} est aussi Cₙ.

Les nombres de Catalan satisfont la récurrence C₀ = 1 et Cₙ₊₁ = Σᵢ₌₀ⁿ Cᵢ Cₙ₋ᵢ. Cette formule reflète la structure « diviser à la racine » commune aux cinq familles bijectives : pour une chaîne de parenthèses, la parenthèse racine « ( » se ferme à une certaine position, divisant la chaîne en deux sous-chaînes équilibrées indépendantes de longueurs 2i et 2(n–i). Sommer sur toutes les positions de division donne la récurrence. La fonction génératrice C(x) = Σ Cₙ xⁿ satisfait x C(x)² – C(x) + 1 = 0, avec pour solution C(x) = (1 – √(1 – 4x)) / (2x).

La raison unificatrice est que toutes les familles de Catalan partagent la même structure récursive : un objet de taille n peut être construit de manière unique en choisissant une « racine » qui divise le reste des données en deux sous-objets indépendants de tailles i et n–1–i (ou similaire), en sommant sur toutes les divisions. C'est exactement la récurrence de Catalan. Les bijections entre ces familles sont souvent élégantes : un « ( » dans une chaîne de parenthèses devient une arête d'enfant gauche dans un arbre binaire et un pas montant dans un chemin de Dyck, de sorte que la donnée combinatoire est littéralement le même objet sous trois costumes différents.

Les nombres de Catalan croissent de manière exponentielle : d'après l'approximation de Stirling, Cₙ ~ 4ⁿ / (n^(3/2) √π). Le rapport Cₙ₊₁/Cₙ = 2(2n+1)/(n+2) converge vers 4, donc chaque nombre de Catalan successif vaut environ quatre fois le précédent. C₁₀ = 16 796 ; C₂₀ ≈ 6,56 × 10¹⁰ ; C₅₀ ≈ 1,37 × 10²⁸. Pour n = 8 (le maximum de cette simulation) C₈ = 1 430 — assez pour dessiner tous les objets individuellement. Au-delà de n ≈ 10, il devient impraticable de tous les énumérer et l'échantillonnage aléatoire doit être utilisé.

Un arbre binaire plein est un arbre enraciné dans lequel chaque nœud interne a exactement deux enfants (jamais un seul). Le nombre d'arbres binaires pleins à n+1 feuilles est Cₙ. Pour n = 3 : C₃ = 5 arbres à 4 feuilles. La bijection vers les chaînes de parenthèses envoie chaque feuille vers « ) » et chaque nœud interne vers « ( », en lisant l'arbre de gauche à droite en préordre. Les arbres binaires pleins sont la structure de l'analyse d'expressions, du codage de Huffman, et de l'arbre de Stern–Brocot pour les fractions. Ils comptent aussi le nombre de façons de parenthéser entièrement un produit de n+1 facteurs — la formulation originale d'Euler du problème (1751).

Euler a compté les triangulations de polygones en 1751 et a trouvé la suite 1, 2, 5, 14, 42, … mais n'avait pas la forme close. Segner a trouvé la récurrence en 1758. Le mathématicien belge Eugène Charles Catalan a donné la formule close Cₙ = (2n)!/((n+1)!n!) en 1838, et la suite porte désormais son nom. Cependant, la suite avait été découverte encore plus tôt par le mathématicien chinois Ming Antu vers 1730, en lien avec des formules de développement trigonométrique. L'histoire de leurs découvertes simultanées et indépendantes est un exemple frappant d'universalité mathématique.

Les nombres de Catalan apparaissent en informatique (nombre de permutations triables par pile, nombre d'arbres binaires de recherche distincts à n clés, nombre de fonctions booléennes monotones à 2 variables), en bio-informatique (structures secondaires de l'ARN comptées par leur structure de parenthèses non croisées), en physique (diagrammes de Feynman non croisés en théorie quantique des champs planaire, moments de la loi du demi-cercle de Wigner en théorie des matrices aléatoires), et en linguistique (nombre d'arbres d'analyse pour une grammaire hors-contexte ambiguë avec une structure de règles spécifique). L'ouvrage « Catalan Numbers » (2015) de Stanley répertorie 214 interprétations combinatoires distinctes.