Nombres de Catalan
Les nombres de Catalan forment une suite d'entiers naturels qui apparaît dans un grand nombre de problèmes de dénombrement. Ils permettent notamment de compter certaines structures récursives, comme les arbres binaires, les parenthésages valides, les chemins dans une grille, les triangulations d'un polygone et plusieurs configurations non croisées.
Cette suite occupe une place importante en combinatoire, en théorie des graphes, dans l'analyse des algorithmes et dans l'étude des structures de données. Elle apparaît chaque fois qu'un objet complexe peut être construit en séparant récursivement un problème en deux sous-problèmes indépendants.
En programmation, les nombres de Catalan servent à estimer le nombre de formes possibles d'un arbre, à compter les expressions correctement parenthésées, à analyser les arbres binaires de recherche, à générer des structures syntaxiques et à étudier la croissance combinatoire de certains espaces de solutions.
Définition
Le nombre de Catalan d'indice n est généralement noté :
| Cn |
Il peut être défini par la formule fermée suivante :
|
Cn = 1/(n+1) × C(2n,n) |
où :
| C(2n,n) |
représente le coefficient binomial :
| (2n)!/(n!n!) |
On obtient donc également :
|
Cn = (2n)!/ ((n+1)!n!) |
Premières valeurs
Les premières valeurs de la suite de Catalan sont :
|
C0 = 1 C1 = 1 C2 = 2 C3 = 5 C4 = 14 C5 = 42 C6 = 132 C7 = 429 C8 = 1430 C9 = 4862 C10 = 16796 |
La suite commence donc par :
| 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ... |
Calcul direct
Pour calculer :
| C4 |
on utilise :
|
C4 = 1/5 × C(8,4) |
Or :
| C(8,4) = 70 |
Donc :
| C4 = 70/5 = 14 |
Relation de récurrence
Les nombres de Catalan peuvent aussi être définis par la relation de récurrence :
| C0 = 1 |
et, pour :
| n ≥ 0 |
|
Cn+1 = ∑i=0n CiCn-i |
Cette relation exprime chaque nombre de Catalan comme une somme de produits de nombres précédents.
Exemple de récurrence
Pour calculer :
| C3 |
on utilise :
|
C3 = C0C2 + C1C1 + C2C0 |
Donc :
|
C3 = 1×2 + 1×1 + 2×1 |
soit :
| C3 = 5 |
Interprétation récursive
La récurrence des nombres de Catalan apparaît lorsqu'une structure peut être séparée autour d'un élément central.
Pour chaque position possible de cet élément :
- une structure se trouve à gauche ;
- une autre structure se trouve à droite.
Si la partie gauche contient i éléments et la partie droite contient n-i éléments, le nombre total de structures pour ce choix est :
| CiCn-i |
En additionnant toutes les séparations possibles, on obtient :
|
Cn+1 = ∑i=0n CiCn-i |
Parenthésages valides
Les nombres de Catalan comptent le nombre de façons de parenthéser correctement une suite de paires de parenthèses.
Pour :
| n = 3 |
les cinq expressions valides sont :
|
((())) (()()) (())() ()(()) ()()() |
On obtient donc :
| C3 = 5 |
Parenthèses bien équilibrées
Une chaîne de parenthèses est correctement équilibrée lorsque :
- chaque parenthèse ouvrante possède une parenthèse fermante correspondante ;
- aucun préfixe de la chaîne ne contient davantage de parenthèses fermantes que de parenthèses ouvrantes ;
- le nombre total de parenthèses ouvrantes est égal au nombre total de parenthèses fermantes.
Le nombre de chaînes valides comportant n paires de parenthèses est :
| Cn |
Exemple avec deux paires
Avec deux paires de parenthèses, les chaînes valides sont :
|
(()) ()() |
Il existe donc :
| C2 = 2 |
possibilités.
Chemins de Dyck
Un chemin de Dyck de longueur 2n est un chemin dans une grille qui :
- commence au point (0,0) ;
- utilise des pas montants et descendants ;
- ne passe jamais sous l'axe horizontal ;
- revient sur l'axe après 2n pas.
Le nombre de chemins de Dyck de longueur 2n est :
| Cn |
Représentation des parenthèses par un chemin
Une parenthèse ouvrante peut être représentée par un pas montant :
|
( → +1 |
Une parenthèse fermante peut être représentée par un pas descendant :
|
) → -1 |
Une expression correctement parenthésée correspond alors exactement à un chemin de Dyck.
Chemins dans une grille carrée
Les nombres de Catalan comptent également les chemins allant de :
| (0,0) |
à :
| (n,n) |
en utilisant seulement :
- un déplacement vers la droite ;
- un déplacement vers le haut ;
sans jamais passer au-dessus de la diagonale :
| y = x |
Le nombre de ces chemins est :
| Cn |
Dénombrement des chemins valides
Le nombre total de chemins de :
| (0,0) |
à :
| (n,n) |
est :
| C(2n,n) |
Parmi eux, certains franchissent la diagonale interdite.
En utilisant un argument de réflexion, on montre que le nombre de chemins invalides est :
| C(2n,n+1) |
Le nombre de chemins valides est donc :
|
C(2n,n) - C(2n,n+1) |
Cette expression se simplifie en :
|
Cn = 1/(n+1) × C(2n,n) |
Principe de réflexion
Le principe de réflexion permet de transformer chaque chemin invalide en un autre chemin plus facile à compter.
On repère le premier point où le chemin dépasse la diagonale, puis on réfléchit la portion initiale du chemin.
Cette transformation établit une bijection entre :
- les chemins invalides ;
- certains chemins possédant un nombre différent de pas horizontaux et verticaux.
Cette méthode donne une démonstration classique de la formule fermée des nombres de Catalan.
Arbres binaires complets
Un arbre binaire complet est un arbre dans lequel chaque noud interne possède exactement deux enfants.
Le nombre d'arbres binaires complets comportant n noeuds internes est :
| Cn |
Chaque arbre peut être décomposé en :
- une racine ;
- un sous-arbre gauche ;
- un sous-arbre droit.
Décomposition des arbres binaires
Supposons qu'un arbre comporte :
| n+1 |
noeuds internes.
Si son sous-arbre gauche contient i noeuds internes, le sous-arbre droit en contient :
| n-i |
Le nombre de possibilités pour cette séparation est :
| CiCn-1 |
En additionnant toutes les valeurs possibles de i, on retrouve la récurrence :
|
Cn+1 = ∑i=0n CiCn-1 |
Arbres binaires ordonnés
Les nombres de Catalan comptent aussi le nombre d'arbres binaires ordonnés distincts comportant n noeuds.
Dans un arbre ordonné, les sous-arbres gauche et droit sont distingués.
Deux arbres ayant la même structure générale, mais dont les sous-arbres sont inversés, sont donc considérés comme différents.
Arbres binaires de recherche
Le nombre de formes différentes d'arbres binaires de recherche pouvant être construites avec n clefs distinctes est :
| Cn |
La valeur des clefs détermine leur position relative, mais pas la forme exacte de l'arbre.
Chaque choix de racine divise les autres clefs en :
- clefs plus petites ;
- clefs plus grandes.
Cette décomposition produit encore la récurrence de Catalan.
Exemple avec trois clefs
Avec les clefs :
| 1, 2, 3 |
il existe cinq formes possibles d'arbres binaires de recherche.
Ainsi :
| C3 = 5 |
Ces formes correspondent aux différents choix de racine et aux différentes structures des sous-arbres.
Ordres d'insertion et formes d'arbres
Plusieurs ordres d'insertion peuvent produire la même forme d'arbre binaire de recherche.
Le nombre de Catalan compte les formes possibles, et non le nombre de permutations d'insertion.
Le nombre total d'ordres d'insertion reste :
| n! |
mais plusieurs de ces ordres correspondent à un même arbre.
Parenthésage d'un produit
Considérons un produit de :
| n+1 |
facteurs :
| x0x1...xn |
Le nombre de façons de placer des parenthèses afin de déterminer l'ordre des opérations est :
| Cn |
Par exemple, avec quatre facteurs :
| abcd |
il existe :
| C3 = 5 |
parenthésages complets.
Exemple de parenthésage
Les cinq parenthésages de quatre facteurs sont :
|
((ab)c)d (ab)(cd) (a(bc))d a((bc)d) a(b(cd)) |
Cette propriété est importante dans l'optimisation de la multiplication de matrices.
Multiplication de chaînes de matrices
Dans un produit de matrices :
| A1A2...An |
l'ordre des matrices ne peut pas être modifié, mais les parenthèses peuvent être placées de plusieurs façons.
Le nombre de parenthésages complets de n matrices est :
| Cn-1 |
La programmation dynamique permet ensuite de trouver le parenthésage minimisant le nombre d'opérations.
Triangulation d'un polygone
Une triangulation consiste à diviser un polygone convexe en triangles à l'aide de diagonales qui ne se croisent pas.
Le nombre de triangulations d'un polygone convexe comportant :
| n+2 |
sommets est :
| Cn |
Exemple de triangulation
Un pentagone convexe possède :
| 5 |
triangulations.
Comme :
| 5 = 3+2 |
on obtient :
| C3 = 5 |
Décomposition d'une triangulation
On choisit un côté fixe du polygone.
Chaque triangle utilisant ce côté partage le polygone en deux sous-polygones.
Le nombre de triangulations est alors le produit du nombre de triangulations des deux sous-polygones.
En additionnant tous les choix possibles du troisième sommet, on retrouve la récurrence de Catalan.
Diagonales non croisées
Les nombres de Catalan comptent également plusieurs configurations de segments non croisés.
Par exemple, le nombre de façons d'associer :
| 2n |
points placés sur un cercle par des cordes qui ne se croisent pas est :
| Cn |
Chaque point doit être relié exactement à un autre point.
Appariements non croisés
Pour :
| n = 3 |
on place 6 points sur un cercle.
Le nombre d'appariements parfaits non croisés est :
| C3 = 5 |
Les appariements qui produisent des croisements ne sont pas comptés.
Empilement et dépilement
Les nombres de Catalan comptent certaines séquences valides d'opérations sur une pile.
Supposons qu'on effectue :
| n |
opérations d'empilement et :
| n |
opérations de dépilement.
La pile ne doit jamais être dépilée lorsqu'elle est vide.
Le nombre de séquences valides est :
| Cn |
Correspondance avec les parenthèses
On peut associer :
|
Empiler → ( |
et :
|
Dépiler → ) |
Une séquence valide d'opérations de pile correspond donc à une expression correctement parenthésée.
Cette bijection explique pourquoi les nombres de Catalan interviennent dans l'analyse des piles.
Ordres de sortie d'une pile
Les nombres de Catalan comptent également certains ordres de sortie possibles lorsqu'une suite d'éléments est introduite dans une pile dans un ordre fixé.
Toutes les permutations ne peuvent pas être produites par une seule pile.
Le nombre de permutations de pile valides pour n éléments est :
| Cn |
dans certaines formulations classiques.
Partitions non croisées
Une partition d'un ensemble circulaire est dite non croisée lorsqu'aucun bloc ne produit de croisements avec un autre bloc lorsqu'on relie leurs éléments.
Le nombre de partitions non croisées d'un ensemble de n éléments est :
| Cn |
Cette interprétation intervient dans la combinatoire avancée et certaines branches de la théorie des probabilités.
Expressions syntaxiques
Dans un compilateur, certaines expressions peuvent être représentées par des arbres syntaxiques binaires.
Le nombre de formes possibles pour une expression comportant n opérateurs binaires est :
| Cn |
Cette quantité mesure la croissance du nombre de structures syntaxiques possibles.
Analyse syntaxique
Lorsqu'une grammaire est ambiguë, une même suite de symboles peut posséder plusieurs arbres syntaxiques.
Pour une suite d'opérations binaires sans règles de priorité, le nombre d'arbres de dérivation possibles peut suivre les nombres de Catalan.
Cette croissance explique pourquoi les ambiguïtés grammaticales doivent être contrôlées dans les compilateurs.
Formule multiplicative
Les nombres de Catalan peuvent être calculés successivement à partir de :
| C0 = 1 |
et :
|
Cn+1 = Cn × 2(2n+1)/(n+2) |
On peut aussi écrire :
|
Cn = Cn-1 × 2(2n-1)/(n+1) |
pour :
| n ≥ 1 |
Cette formule permet un calcul itératif efficace.
Exemple avec la formule multiplicative
À partir de :
| C3 = 5 |
on calcule :
|
C4 = 5 × 2(2×3+1)/(3+2) |
Donc :
|
C4 = 5 × 14/5 |
soit :
| C4 = 14 |
Intégralité du résultat
La formule :
|
1/(n+1) × C(2n,n) |
semble contenir une division pouvant produire une fraction.
Cependant, le résultat est toujours entier.
Cette propriété découle notamment de l'interprétation combinatoire du nombre de Catalan, puisqu'il compte un ensemble fini d'objets.
Différence de coefficients binomiaux
Une autre formule est :
|
Cn = C(2n,n) - C(2n,n+1) |
Cette forme montre directement que le résultat est entier.
Elle apparaît naturellement dans le dénombrement des chemins qui restent sous une diagonale.
Identité avec les coefficients binomiaux
Comme :
|
C(2n,n+1) = n/(n+1) × C(2n,n) |
on obtient :
|
C(2n,n) - C(2n,n+1) |
|
= C(2n,n) ( 1 - n/(n+1) ) |
|
= 1/(n+1) × C(2n,n) |
Fonction génératrice
La fonction génératrice des nombres de Catalan est :
|
C(x) = ∑n=0∞ Cnxn |
La relation de récurrence conduit à l'équation :
|
C(x) = 1 + xC(x)2 |
Résolution de la fonction génératrice
L'équation :
|
xC(x)2 - C(x) + 1 = 0 |
est une équation quadratique en :
| C(x) |
Sa résolution donne :
|
C(x) = (1 ± √(1-4x))/(2x) |
La solution compatible avec :
| C(0)=1 |
est :
|
C(x) = (1-√(1-4x))/(2x) |
Développement en série
Le développement de la fonction génératrice produit :
|
C(x) = 1 + x + 2x2 + 5x3 + 14x4 + 42x5 + ... |
Le coefficient de :
| xn |
est précisément :
| Cn |
Convolution
La récurrence :
|
Cn+1 = ∑i=0n CiCn-i |
est une convolution de la suite avec elle-même.
Dans la fonction génératrice, une convolution correspond à une multiplication :
| C(x)2 |
Cette correspondance explique naturellement l'équation :
|
C(x) = 1+xC(x)2 |
Croissance asymptotique
Les nombres de Catalan croissent approximativement comme :
|
Cn ≈ 4n/ (n^(3/2)√π) |
Cette approximation montre que la croissance est exponentielle, avec un facteur principal proche de :
| 4n |
mais divisée par une puissance de n.
Conséquence algorithmique
Même si les nombres de Catalan croissent moins rapidement que :
| 4n |
ils deviennent rapidement très grands.
Par exemple :
| C20 = 6 564 120 420 |
et :
| C30 = 3 814 986 502 092 304 |
L'énumération de toutes les structures correspondantes devient donc rapidement impraticable.
Comparaison avec la factorielle
La croissance de :
| Cn |
est exponentielle.
La croissance de :
| n! |
est encore plus rapide.
On peut donc retenir approximativement :
|
Cn < 4n < n! |
pour des valeurs suffisamment grandes de n, bien que la comparaison exacte dépende de la valeur considérée.
Calcul récursif naïf
La relation de récurrence peut être programmée directement :
|
MODULE Catalan(n) SI n ≤ 1 ALORS RETOURNER 1 FIN SI résultat ← 0 POUR i ← 0 JUSQU'A n-1 résultat ← résultat + Catalan(i) × Catalan(n-1-i) FIN POUR RETOURNER résultat |
Cette méthode est simple, mais très inefficace.
Complexité de la récursion naïve
Le calcul récursif recalcule plusieurs fois les mêmes valeurs.
Sa complexité augmente exponentiellement.
Il devient rapidement inutilisable, même pour des valeurs modérées de n.
La mémoïsation ou la programmation dynamique est donc préférable.
Calcul par programmation dynamique
|
MODULE CatalanDP(n) C[0] ← 1 POUR i ← 1 JUSQU'A n C[i] ← 0 POUR j ← 0 JUSQU'A i-1 C[i] ← C[i] + C[j] × C[i-1-j] FIN POUR FIN POUR RETOURNER C[n] |
Complexité de la programmation dynamique
La boucle externe parcourt :
| n |
valeurs.
Pour chaque valeur, la boucle interne effectue jusqu'à :
| n |
opérations.
La complexité temporelle est donc :
| O(n2) |
La mémoire utilisée est :
| O(n) |
Calcul par coefficient binomial
On peut calculer :
|
Cn = C(2n,n)/(n+1) |
Si le coefficient binomial est calculé de manière multiplicative, la complexité peut être réduite à :
| O(n) |
opérations arithmétiques.
Il faut cependant utiliser des types numériques suffisamment grands.
Algorithme multiplicatif
|
MODULE CatalanBinomial(n) coefficient ← 1 POUR i ← 1 JUSQU'A n coefficient ← coefficient × (n+i) DIV i FIN POUR RETOURNER coefficient DIV (n+1) |
Ce calcul produit d'abord :
| C(2n,n) |
puis effectue la division finale.
Calcul progressif sans coefficient complet
|
MODULE CatalanProgressif(n) résultat ← 1 POUR i ← 0 JUSQU'A n-1 résultat ← résultat × 2(2i+1) DIV (i+2) FIN POUR RETOURNER résultat |
Chaque étape produit exactement le nombre de Catalan suivant.
Précision des divisions
Lors d'un calcul en entiers, l'ordre des multiplications et des divisions est important.
Une division effectuée trop tôt peut supprimer une partie du résultat par troncature.
Il faut s'assurer que chaque division est exacte ou utiliser des fractions simplifiées, des entiers multiprécision ou un calcul du coefficient binomial correctement ordonné.
Dépassement de capacité
Les nombres de Catalan dépassent rapidement la capacité des types numériques ordinaires.
Pour un entier signé de 32 bits, la dernière valeur représentable est :
| C19 = 1 767 263 190 |
La valeur suivante :
| C20 = 6 564 120 420 |
dépasse la limite de 32 bits signés.
Limite d'un entier signé de 64 bits
Avec un entier signé de 64 bits, plusieurs valeurs supplémentaires peuvent être représentées.
Cependant, la croissance reste rapide et finit également par provoquer un dépassement.
Il est souvent préférable d'utiliser un type multiprécision comme :
| BigInteger |
Exemple en Java
- import java.math.BigInteger;
-
- public final class CatalanNumbers {
-
- private CatalanNumbers() {
- }
-
- public static BigInteger catalan(int n) {
- if (n < 0) {
- throw new IllegalArgumentException(
- "L'indice ne peut pas être négatif."
- );
- }
-
- BigInteger resultat =
- BigInteger.ONE;
-
- for (int i = 0; i < n; i++) {
- resultat = resultat.multiply(
- BigInteger.valueOf(
- 2L * (2L * i + 1L)
- )
- );
-
- resultat = resultat.divide(
- BigInteger.valueOf(i + 2L)
- );
- }
-
- return resultat;
- }
-
- public static void main(String[] args) {
- for (int i = 0; i <= 10; i++) {
- System.out.println(
- "C_" + i + " = " + catalan(i)
- );
- }
- }
- }
Résultat du programme
Le programme affiche :
|
C_0 = 1 C_1 = 1 C_2 = 2 C_3 = 5 C_4 = 14 C_5 = 42 C_6 = 132 C_7 = 429 C_8 = 1430 C_9 = 4862 C_10 = 16796 |
Génération des parenthèses valides
Les nombres de Catalan peuvent être utilisés pour prévoir le nombre de chaînes que produira un algorithme de génération de parenthèses.
|
MODULE GénérerParenthèses(ouvertes,fermées,n,chaîne) SI longueur(chaîne)=2n ALORS AFFICHER chaîne RETOURNER FIN SI SI ouvertes ← n ALORS GénérerParenthèses( ouvertes+1, fermées, n, chaîne+"(" ) FIN SI SI fermées < ouvertes ALORS GénérerParenthèses( ouvertes, fermées+1, n, chaîne+")" ) FIN SI |
Complexité de la génération
L'algorithme produit exactement :
| Cn |
chaînes.
Comme chaque chaîne possède une longueur :
| 2n |
le temps total nécessaire pour les construire ou les afficher est au moins :
| O(nCn) |
Cette complexité est inévitable si toutes les solutions doivent être générées.
Validation d'une chaîne de parenthèses
Une chaîne peut être validée à l'aide d'un compteur.
|
MODULE ParenthèsesValides(chaîne) compteur ← 0 POUR CHAQUE caractère DANS chaîne SI caractère="(" ALORS compteur ← compteur+1 SINON compteur ← compteur-1 FIN SI SI compteur < 0 ALORS RETOURNER FAUX FIN SI FIN POUR RETOURNER compteur=0 |
Une chaîne valide correspond à un chemin de Dyck.
Rang d'un objet de Catalan
Dans certaines applications, il est utile d'associer à chaque structure de Catalan un numéro appelé rang.
On peut ainsi :
- ordonner les parenthésages ;
- accéder à une structure sans toutes les générer ;
- compresser une représentation ;
- produire la structure correspondant à un indice donné.
Ces opérations utilisent généralement des tableaux de nombres de Catalan et des méthodes de dénombrement récursif.
Échantillonnage aléatoire
Pour générer uniformément une structure de Catalan aléatoire, il ne suffit pas de choisir au hasard une séparation gauche-droite.
La probabilité de choisir une séparation i doit être proportionnelle à :
| CiCn-1-i |
Cette pondération garantit que chaque structure finale possède la même probabilité.
Nombres de Catalan modulo un entier
Dans certains problèmes algorithmiques, on demande :
| Cn mod m |
plutôt que la valeur exacte.
Si m est premier, on peut utiliser :
- les factorielles modulo m ;
- les inverses modulaires ;
- le petit théorème de Fermat.
On calcule alors :
|
Cn ≡ (2n)! × (n!)-2 × (n+1)-1 (mod m) |
à condition que les inverses existent.
Module non premier
Lorsque le module n'est pas premier, la division modulaire devient plus délicate.
Il n'est pas toujours possible d'inverser :
| n+1 |
ou les factorielles.
On peut alors utiliser :
- une programmation dynamique ;
- une décomposition en facteurs premiers ;
- le théorème chinois des restes ;
- des méthodes spécialisées sur les valuations premières.
Triangle de Catalan
Les nombres de Catalan peuvent être étendus à un tableau appelé triangle de Catalan.
Ce triangle contient plusieurs familles de nombres reliées aux chemins de grille et aux parenthésages partiels.
Il permet d'étudier des structures où certaines contraintes sont incomplètes ou où le chemin se termine à une hauteur donnée.
Nombres de Narayana
Les nombres de Narayana raffinent les nombres de Catalan.
Ils comptent les chemins de Dyck de longueur 2n possédant exactement k sommets ou, selon l'interprétation, certains nombres précis de blocs ou de pics.
Ils sont définis par :
|
N(n,k) = 1/n × C(n,k) × C(n,k-1) |
La somme des nombres de Narayana pour un n fixé donne :
| Cn |
Relation avec les nombres de Schröder
Les nombres de Schröder comptent certaines structures similaires à celles de Catalan, mais autorisent des opérations supplémentaires.
Par exemple, dans certains chemins, ils permettent un pas diagonal en plus des pas horizontaux et verticaux.
Ils constituent une généralisation de plusieurs problèmes comptés par les nombres de Catalan.
Relation avec les nombres de Motzkin
Les nombres de Motzkin comptent des chemins comportant :
- des pas montants ;
- des pas descendants ;
- des pas horizontaux ;
sans passer sous l'axe.
Ils sont proches des nombres de Catalan, mais décrivent une famille plus large de structures.
Applications en théorie des graphes
Les nombres de Catalan apparaissent dans :
- certains arbres planaires ;
- les triangulations ;
- les appariements non croisés ;
- les dissections de polygones ;
- certaines familles de graphes extérieurs planaires ;
- les chemins monotones contraints.
Ils constituent donc un outil central de la combinatoire des graphes planaires.
Applications en compilation
Dans les compilateurs, les nombres de Catalan interviennent dans :
- le nombre d'arbres syntaxiques binaires ;
- le parenthésage des expressions ;
- l'analyse d'ambiguïtés grammaticales ;
- la génération de tests syntaxiques ;
- la construction d'arbres d'expression ;
- l'optimisation de l'ordre des opérations.
Applications en structures de données
Les nombres de Catalan sont utilisés pour compter :
- les formes d'arbres binaires ;
- les arbres binaires de recherche ;
- certaines structures de tas ;
- les séquences d'opérations de pile ;
- les parenthésages ;
- les configurations récursives non croisées.
Ils permettent d'estimer la taille d'un espace de structures possibles.
Applications en algorithmique
Les nombres de Catalan apparaissent notamment dans :
- la programmation dynamique ;
- la génération exhaustive ;
- les algorithmes de retour arrière ;
- les problèmes de parenthésage ;
- les arbres de recherche ;
- les algorithmes sur les polygones ;
- les structures syntaxiques ;
- les chemins contraints ;
- le dénombrement combinatoire.
Tableau récapitulatif
| Objet compté | Nombre |
|---|---|
| Parenthésages valides avec n paires | Cn |
| Chemins de Dyck de longueur 2n | Cn |
| Arbres binaires complets avec n noeuds internes | Cn |
| Formes d'arbres binaires de recherche avec n clefs | Cn |
| Triangulations d'un polygone à n+2 sommets | Cn |
| Parenthésages complets de n+1 facteurs | Cn |
| Appariements non croisés de 2n points | Cn |
| Séquences valides de n empilements et n dépilements | Cn |
| Partitions non croisées d'un ensemble de n éléments | Cn |
Avantages
Les nombres de Catalan présentent plusieurs avantages :
- ils unifient de nombreux problèmes de dénombrement ;
- ils décrivent naturellement des structures récursives ;
- ils possèdent une formule fermée ;
- ils possèdent une relation de récurrence simple ;
- ils peuvent être calculés par programmation dynamique ;
- ils disposent d'une fonction génératrice élégante ;
- ils apparaissent dans de nombreuses structures informatiques ;
- ils permettent d'estimer la taille d'espaces de recherche ;
- ils établissent des liens entre les arbres, les chemins, les parenthèses et les polygones.
Limites et précautions
Plusieurs précautions doivent être prises :
- les nombres de Catalan augmentent rapidement ;
- les types numériques ordinaires débordent rapidement ;
- la récursion naïve est très inefficace ;
- l'énumération exhaustive devient rapidement impraticable ;
- les objets comptés doivent respecter précisément les contraintes de Catalan ;
- un problème ressemblant à un problème de Catalan peut nécessiter une autre suite ;
- l'ordre des divisions est important dans les calculs entiers ;
- le calcul modulo un entier non premier nécessite des méthodes particulières ;
- compter les structures ne fournit pas automatiquement une méthode efficace pour les générer.
Remarque
Les nombres de Catalan constituent l'une des suites les plus importantes de la combinatoire. Leur présence dans des problèmes très différents s'explique par une structure récursive commune : un objet peut souvent être séparé en une partie gauche et une partie droite, chacune étant elle-même un objet du même type.
En programmation, ils permettent de compter les arbres binaires, les parenthésages, les chemins valides, les triangulations et les séquences d'opérations de pile. Leur croissance rapide illustre également le phénomène d'explosion combinatoire et montre pourquoi les algorithmes de génération exhaustive deviennent coûteux. Ils préparent naturellement à l'étude des nombres de Narayana, des nombres de Motzkin, des nombres de Schröder, des fonctions génératrices et de la combinatoire des arbres.