Après les nombres de Mersenne, voici les nombres de Catalan ! Les nombres de Catalan sont une suite d’entiers naturels utilisée en dénombrement. Voyons ensemble leur définition, diverses propriétés et quelques applications !
Définition des nombres de Catalan
On peut définir les nombres de Catalan par des coefficients binomiaux, en voici leur définition ! Le n-ième nombre de Catalan, noté Cn, est défini par
C_n = \dfrac{1}{n+1} \binom{2n}{n}On peut les réécrire avec des factorielles par :
C_n = \dfrac{(2n)!}{(n+1)!n!} Ou encore, avec un produit ou une différence de coefficients binomiaux :
C_n =\prod_{k=2}^n \dfrac{n+k}{k} = \binom{2n}{n} - \binom{2n}{n+1}Les 15 premiers nombres de Catalan sont
- 1
- 1
- 2
- 5
- 14
- 42
- 132
- 429
- 1430
- 4862
- 16796
- 58786
- 208012
- 742900
- 2674440
Propriétés des nombres de Catalan
Première propriété : Equivalent
On peut leur chercher un équivalent. Pour cela, on va utiliser la formule de Stirling sur la définition avec des factorielles :
\begin{array}{ll}
C_n &= \dfrac{(2n)!}{(n+1)!n!} \\
& \sim \dfrac{\sqrt{2\pi 2n} \left( \frac{2n}{e}\right)^{2n}}{\sqrt{2\pi (n+1)} \left( \frac{n+1}{e}\right)^{n+1}\sqrt{2\pi n} \left( \frac{n}{e}\right)^n}\\
& \sim \dfrac{2\sqrt{\pi n} \left( \frac{2n}{e}\right)^{2n}}{2\sqrt{\pi n} \left( \frac{n+1}{e}\right)^{n+1}\sqrt{\pi n} \left( \frac{n}{e}\right)^n}\\
& \sim \dfrac{ \left( \frac{2n}{e}\right)^{2n}}{\left( \frac{n+1}{e}\right)^{n+1}\sqrt{\pi n} \left( \frac{n}{e}\right)^n}\\
& \sim \dfrac{4^ne^{n+n+1-2n} n^{2n}}{\left( n+1\right)^{n+1}\sqrt{\pi n} n^n}\\
& \sim \dfrac{4^ne n^{2n}}{n^{n+1}\left( 1+\frac{1}{n}\right)^{n+1}\sqrt{\pi n} n^n}\\
& \sim \dfrac{4^ne n^{2n}}{n^{n+1}e\sqrt{\pi n} n^n}\\
& \sim \dfrac{4^n n^{2n-n-(n+1)}}{\sqrt{\pi n} }\\
& \sim \dfrac{4^n}{n\sqrt{n\pi} }\\
\end{array}Parité
Le nombre de Catalan Cn est impair si et seulement si n = 2k – 1
Relation de récurrence
Les nombres de Catalan vérifient la formule de récurrence suivante :
C_0=1,C_{n+1} = \sum_{k=0}^n C_i C_{n-i}En utilisant cette formule en tant que produit de Cauchy, on obtient la série entière suivante :
\dfrac{1-\sqrt{1-4x}}{2x}=\sum_{n=0}^{+\infty} C_n x^n De plus, notons que :
\sum_{n+0}^{+\infty} \dfrac{1}{C_n} = 2 + \dfrac{4\pi}{9 \sqrt{3}}Représentation intégrale
Une écriture intégrale de Cn est :
C_n = \dfrac{1}{\pi} \int_0^2 x^{2n}\sqrt{4-x^2}dxReprésentation fonctionnelle
Si on cherche une fonction continue C telle que C(n) = Cn, et même une fonction indéfiniment dérivable et même méromorphe pour ceux qui connaissent l’analyse complexe. Alors, l’unique fonction méromorphe qui convient et qui est une fonction qui convient est :
C(s) =\dfrac{\Gamma(2s + 1)}{\Gamma(s + 1)\Gamma(s + 2)}Où Γ est la fonction Gamma dont nous avions parlé dans un article précédent
Applications des nombres de Catalan
Comme vous allez le voir sur la suite, les nombres de Catalan apparaissent dans diverses applications liées à du dénombrement.
Mots de Dyck
Un mot de Dyck est une chaine de caractères formée de n lettres X et n lettres Y. Un tel mot ne doit avoir aucun préfixé contenant strictement plus de X que de Y. Par exemple, les mots de Dyck de longueur 2 sont :
- XXYY
- XYXY
Ce qui correspond bien à C2. Cn est donc le nombre de mots de Dyck formé de n lettres X et Y.
On obtient le corollaire suivant : Le nombre de vecteurs de {-1;1}2n dont les sommes partielles des coordonées soient toutes positive et dont la somme totale soit nulle vaut Cn.
Triangulations de polygônes
Si on découpe un polygône convexe à n+2 côtés en reliant certains de ses sommets par des segments, on a Cn manières de le faire. Exemple avec n = 3 et le pentagone :
Associativité
Le nombre de façons de calculer un produit non associatif de n + 1 termes vaut Cn.
Arbres binaires
Et pour finir, une dernière application : Cn est le nombre d’arbres binaires à n noeuds.
