Certains nombres reviennent dans des problèmes sans lien apparent : la même suite compte les façons de mettre des parenthèses autour d’un produit, de découper un polygone en triangles et de tracer un chemin qui ne franchit jamais la diagonale. Ce sont les nombres de Catalan. Ce calculateur donne le nombre de Catalan pour un n choisi, les structures qu’il dénombre, le coefficient binomial central dont il provient et une approximation simple avec son erreur.
Comment se fait le calcul
- Nombre de Catalan C(n) = (2n)! ÷ ((n + 1)! × n!) = C(2n, n) ÷ (n + 1)
- Triangulations d’un polygone convexe à n + 2 côtés = C(n)
- Parenthésages d’un produit de n + 1 facteurs = C(n)
- Approximation C(n) ≈ 4ⁿ ÷ (n^1,5 × √π)
- Rapport de croissance C(n) ÷ C(n − 1) tend vers 4
Exemple
Pour n = 10, le nombre de Catalan est 16 796. Il compte les façons de trianguler un polygone à 12 côtés, de parenthéser un produit de 11 facteurs et les suites valides de 10 paires de parenthèses. Le coefficient binomial central C(20, 10) vaut 184 756, et l’approximation donne environ 18 708, soit 11,4 % de trop. Le rapport C(10) ÷ C(9) est de 3,455, déjà proche de 4.
Pourquoi c’est important
Les nombres de Catalan répondent à un nombre surprenant de problèmes de dénombrement, de la structure des expressions dans un compilateur aux formes des arbres binaires de recherche. Connaître la vitesse de croissance avertit que lister tous les cas devient vite impossible : C(20) vaut déjà 6,5 milliards. L’approximation donne l’ordre de grandeur sans calculer de factorielles.
Bon à savoir
Le calcul est exact jusqu’à n = 17, valeur pour laquelle le nombre tient largement dans la précision du calcul. L’approximation s’améliore lentement, avec une erreur d’environ 1/(8n). Des problèmes de dénombrement différents donnent les mêmes nombres seulement s’ils sont posés avec la bonne contrainte, comme un chemin qui reste d’un côté de la diagonale. Cet outil est pédagogique.
En pratique
Pour vérifier un problème de dénombrement, calculez à la main les quatre premières valeurs et comparez-les à 1, 2, 5, 14 : si elles coïncident, un nombre de Catalan est probable. Pour le nombre de façons d’évaluer une expression à n opérations, utilisez C(n).
Outils associés
Le calculateur de permutations, celui de Fibonacci et celui des suites arithmétiques et géométriques traitent d’autres suites classiques de dénombrement.