Les nombres de Catalan : Propriétés et applications

Découvrez les nombres de Catalan, ces nombres qui ont de nombreuses applications !
Catalogne

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}dx

Repré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.

Total
0
Partages

Laisser un commentaire

Articles similaires