Nombres de Catalan
Considérons une expression de la forme $a_1 T a_2 T \cdots T a_n$, où $T$ désigne un des signes $+$ ou $-$. On souhaite placer des parenthèses dans cette expression de sorte qu'il n'y ait aucune ambigüité dans l'ordre à adopter pour effectuer les opérations, et éviter les problèmes du type $1-3+7$, qui peut être compris $1-(3+7)$ ou $(1-3)+7$, ce qui ne donne pas le même résultat! Il s'agit donc de placer des parenthèses autour des termes de sorte que :
- on n'ait jamais plus de deux termes non parenthésés (pas de choix à faire!).
- on ne mette jamais des parenthèses autour d'un seul terme (pas de parenthèses inutiles!).
Le nombre de façons de bien parenthéser cette expression s'appelle nombre de Catalan d'ordre $n$, et nous le noterons $C_n$. Calculons ce nombre pour les premières valeurs de $n$ :
- pour $n=1$, une seule façon : $a$.
- pour $n=2$, une seule façon : $aTb$.
- pour $n=3$, 2 façons : $(aTb)Tc$ ou $aT(bTc)$.
- pour $n=4$, 5 façons : $(aTb)T(bTc)$, $aT( (bTc)Td )$, $aT(bT(CTd))$, $((aTb)Tc)Td$, $(aT(bTc))Td$.
Il est facile d'obtenir une relation de récurrence pour calculer les nombres de Catalan. Si l'on souhaite obtenir un parenthésage de $(n+1)$ termes, on regarde l'opération la plus externe : $b_1T b_2$, où $b_1$ et $b_2$ sont eux-mêmes le résultat obtenu après parenthésage de $p$ termes pour $b_1$, et de $n+1-p$ termes pour $b_2$. Comme $p$ peut être quelconque entre $1$ et $n,$ on obtient la relation de récurrence $$C_{n+1}=\sum_{p=1}^n C_p C_{n+p-1}.$$ On peut alors déterminer une formule pour $C_n$ grâce à la théorie des séries entières (ou celle des séries génératrices). On trouve $$C_n=\frac{\binom{2n-2}{n-1}}{n}.$$
Les nombres de Catalan interviennent dans de nombreux problèmes de combinatoire. Par exemple, Euler les avait introduits pour calculer le nombre de façons qu'il y a de partager un polygone convexe à $n$ côtés à l'aide de ses diagonales sans que celles-ci ne se coupent.