Les nombres de Catalan

Des profils de montagne qui ne passent jamais sous le niveau de la mer, ou des parenthèses bien écrites : on les trace, on les compte, et une symétrie démontre la formule $C_n = \dfrac{1}{n+1}\dbinom{2n}{n}$.

On trace pas à pas un chemin de $n$ montées et $n$ descentes, pour $n$ de $1$ à $8$ ; s'il ne passe jamais sous le niveau $0$, c'est un chemin de Dyck, et il se lit comme une écriture correcte de $n$ paires de parenthèses. La page montre tous les chemins de Dyck jusqu'à $n = 4$, compte les chemins quelconques et ceux qui passent sous $0$, et dessine la symétrie qui transforme un mauvais chemin en un chemin finissant au niveau $-2$.

Ce que cela signifie : cette symétrie par rapport à la droite de niveau $-1$, appliquée à partir du premier contact, met en bijection les mauvais chemins et les chemins de $n - 1$ montées et $n + 1$ descentes. Il y a donc $\dbinom{2n}{n+1}$ mauvais chemins, et $C_n = \dbinom{2n}{n} - \dbinom{2n}{n+1} = \dfrac{1}{n+1}\dbinom{2n}{n}$ : $1$, $2$, $5$, $14$, $42$, $132$, $429$, $1\,430$ pour $n$ de $1$ à $8$. Le découpage au premier retour au niveau $0$ donne la récurrence $C_{n+1} = \displaystyle\sum_{k=0}^{n} C_k\,C_{n-k}$.

Le piège le plus courant est de croire qu'il suffit d'autant de parenthèses ouvrantes que de fermantes : pour deux paires, il y a $6$ mots et seulement $2$ écritures correctes.