Aller au contenu
Omnikalc

Nombres de Catalan : C(n) et ce qu'il dénombre

Saisissez n pour obtenir le nombre de Catalan, les triangulations de polygone et parenthésages qu'il compte, le coefficient binomial central et une approximation.

Mis à jour le
Vos paramètres

Valeur hors limites

Résultats

Nombre de Catalan C(n)

16 796

Triangulations d'un polygone convexe à n + 2 côtés
16 796
Parenthésages d'un produit de n + 1 facteurs
16 796
Coefficient binomial central C(2n, n)
184 756
Approximation 4ⁿ ÷ (n^1,5 × √π)
18 708
Erreur de l'approximation
11,4 %
Rapport C(n) ÷ C(n − 1) (tend vers 4)
3,455

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.

Questions fréquentes

Que sont les nombres de Catalan ?

C'est la suite 1, 1, 2, 5, 14, 42, 132, 429, … qui compte de nombreuses structures : parenthésages d'un produit, arbres binaires à n nœuds, triangulations d'un polygone, chemins sur une grille restant sous la diagonale, et suites valides de n paires de parenthèses.

Comment calcule-t-on un nombre de Catalan ?

C(n) = (2n)! ÷ ((n + 1)! × n!), soit C(2n, n) ÷ (n + 1). Les premières valeurs sont 1, 1, 2, 5, 14, 42, 132, 429, 1430 et 4862, et C(10) vaut 16 796.

Combien de triangulations a un polygone ?

Un polygone convexe à n + 2 côtés se découpe en triangles de C(n) façons. Un hexagone (n = 4) a 14 triangulations et un octogone (n = 6) en a 132.

À quelle vitesse croissent-ils ?

Chaque terme vaut environ 4 fois le précédent, car C(n) est proche de 4ⁿ ÷ (n^1,5 × √π). Le rapport entre termes voisins tend vers 4, d'où une croissance très rapide.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.