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

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

17 mai 2022

714 vues

2 minutes de lecture

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 !

Table des matières

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é C_n, 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

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 C_n est impair si et seulement si n = 2^k – 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 C_n 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) = C_n, 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 à C₂. C_n 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}²ⁿ dont les sommes partielles des coordonées soient toutes positive et dont la somme totale soit nulle vaut C_n.

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 C_n manières de le faire. Exemple avec n = 3 et le pentagone :