Calculateur de nombres de Catalan
Calculez les nombres de Catalan avec des applications en combinatoire et arbres binaires
Entrez un entier non négatif (de 0 à 30)
Résultats
Entrez les valeurs et cliquez sur Calculer pour voir le résultat.
Théorie & Formule
Nombres de Catalan
Les nombres de Catalan forment une suite de nombres naturels qui apparaissent dans divers problèmes de dénombrement, souvent impliquant des objets définis récursivement. Le nième nombre de Catalan compte le nombre d'expressions contenant n paires de parenthèses correctement appariées.
Formules
\(C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\)
\(C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}\)
La première formule utilise des coefficients binomiaux, tandis que la seconde est une définition récursive
Applications
- Nombre de façons d'apparier correctement n paires de parenthèses
- Nombre d'arbres binaires différents avec n+1 feuilles
- Nombre de chemins de (0,0) à (n,n) qui ne croisent pas la diagonale
- Nombre de façons de trianguler un polygone convexe à n+2 côtés
- Nombre de façons de relier 2n points sur un cercle avec n cordes non croisées
Premiers nombres de Catalan
Les premiers nombres de Catalan sont: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796...
Exemple
Calculer C₃ (nombre de façons d’apparier 3 paires de parenthèses) :
\(C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \cdot 20 = 5\)