On rappelle que si {0\leq p\leq n}, le symbole {\dbinom np} désigne le nombre de parties à {p} éléments dans un ensemble à {n} éléments. Par convention, on pose {\dbinom np=0} si {p\lt0} ou {p>n}.
Pour tout {n} de {\mathbb N}, {C_n=\dfrac{(2n)!}{n!(n+1)!}} est appelé nombre de Catalan d’indice {n}.
I. Généralités sur les nombres de Catalan
1. (a) Montrer que pour tout entier naturel {n}, on a l’égalité {C_{n+1}=\dfrac{2(2n+1)}{n+2}C_n}.
2. (a) Pour {n\geq1}, {\begin{array}{rcl}C_n&=&\dfrac1{n+1}\dbinom{2n}{n}=\dfrac1n\dbinom{2n}{n+1}\\[8pt]&=&\dbinom{2n}{n}-\dbinom{2n}{n+1}\end{array}}
2. (b) Pour {n\geq2}, {\begin{array}{rcl}C_n&=&\dfrac2{n+1}\dbinom{2n-1}{n}\\[8pt]&=&\dfrac2{n-1}\dbinom{2n-1}{n+1}\\[8pt]&=&\dbinom{2n-1}{n}-\dbinom{2n-1}{n+1}\end{array}}
2. (c) Montrer que les {C_n} sont dans {\mathbb N}, que la suite {(C_n)} est strictement croissante à partir de {n=1}, et en déduire {\lim\limits_{n\to+\infty}C_n=+\infty}.
On va étudier un problème de dénombrement où interviennent les nombres de Catalan.
On considère des chemins joignant des points de {\mathbb N\times\mathbb N}, et formés de déplacements successifs. Les seuls déplacements autorisés à partir d’un point {(n,m)} sont :
Le passage de {(n,m)} à {(n+1,m)}, vers la droite.
Le passage de {(n,m)} à {(n,m+1)}, vers le haut.
On note {\Delta=\{(n,m)\in\mathbb N^2,\ 0\leq m\leq n\}} l’ensemble des points de {\mathbb N^2} qui sont sous ou sur la diagonale {y=x}.
Voici par exemple un chemin de {\Delta}, qui va de {(0,0)} à {(6,5)}.
Remarque : pour tous entiers naturels {a} et {b}, et moyennant une translation de vecteur {(a,b)}, il y a autant de chemins d’origine {(0,0)} et d’extrémité {(n,m)} que de chemins d’origine {(a,b)} et d’extrémité {(a+n,b+m)}.
Pour tout {(n,m)} de {\Delta}, on note {\delta_{n,m}} le nombre de chemins d’origine {(0,0)}, d’extrémité {(n,m)}, et qui sont inclus dans {\Delta} (donc qui ne traversent pas la diagonale).
On note {\delta_n=\delta_{n,n}}, c’est-à-dire le nombre de chemins de {\Delta} qui vont de {(0,0)} à {(n,n)}.
1. (a) Indiquer rapidement la valeur des coefficients {\delta_{n,0}}, pour tout {n} de {\mathbb N}.
1. (d) Former le tableau triangulaire des {\delta_{n,m}} pour {0\leq m\leq n\leq7}. Que remarque-t-on pour les valeurs diagonales {\delta_n}, avec {0\leq n\leq7} ?
2. (a) Montrer que pour tout couple {(n,m)} de {\Delta}, {\delta_{n,m}=\frac{n-m+1}{n+1}\dbinom{n+m}{n}}Indication : procéder par récurrence sur l’entier {n} ; pour chaque valeur de {n}, on sera amené à vérifier l’égalité précédente pour {m=1}, {m=2}, etc., {m=n}.
2. (b) En déduire que le nombre de Catalan {C_n} est égal au nombre {\delta_n} de chemins de {\Delta} qui ont le point {(0,0)} pour origine et le point {(n,n)} pour extrémité.
3. (b) Un chemin {P} de {(0,0)} à {(n,n)} est dit excessif s’il franchit {y=x}. Soit {E_n} le nombre de chemins excessifs de {(0,0)} à {(n,n)}. Prouver {\delta_n=\dbinom{2n}{n}-E_n}.
3. (d) Montrer que la transformation {P\mapsto P^{\prime}} évoquée ci-dessus réalise une bijection de l’ensemble des chemins excessifs qui vont de {(0,0)} à {(n,n)} vers l’ensemble de tous les chemins qui vont de {(0,0)} à {(n-1,n+1)}.
On va maintenant établir une relation de récurrence vérifiée par les {C_n}. Soit {P} un chemin de {\Delta}, d’origine {A(0,0)} et d’extrémité {B(n,n)}, avec {n\geq1}. On sait qu’il y a exactement {C_n} façons de former {P}.
4. (a) On suppose que {P} ne rencontre la diagonale {y=x} qu’en {A} et {B}. Montrer que le nombre de façons différentes de former le chemin {P} est {C_{n-1}}.
4. (b) On suppose que {P} rencontre {y=x} en au moins un point autre que {A} et {B}. Soit {k} l’abscisse minimum (comprise entre 1 et {n-1}) de ces points d’intersection.
Pour chaque valeur de {k}, montrer qu’il y a {C_{k-1}C_{n-k}} façons de former {P}.
III. Interprétations combinatoires des nombres de Catalan
Les nombres de Catalan apparaissent dans de très nombreux problèmes d’énumération. Dans cette partie, où {n} est fixé, on se propose d’aborder certains de ces problèmes.
Dans les questions suivantes, montrer que le nombre évoqué est toujours égal à {C_n}. On notera {S_1,S_2,S_3}, etc., les ensembles énumérés aux questions 1, 2, 3, etc. On notera également {S_0} l’ensemble des chemins de {\Delta} qui vont de {(0,0)} à {(n,n)}.
1. Le nombre de suites {x_1,x_2,\ldots,x_{2n}} de {2n} éléments de {\{-1,1\}} telles que {\begin{array}{c}\displaystyle\sum_{k=1}^{2n}x_k=0\\[8pt]\displaystyle\forall m\in\{1,\ldots,2n\},\ \sum_{k=1}^{m}x_k\geq0\end{array}}Donner les solutions si {n=3}.
2. Le nombre de suites croissantes {y_1\leq y_2\leq\cdots\leq y_{n-1}} de {\mathbb N} avec {y_k\leq k} pour tout {k}. Donner les solutions quand {n=4}.
3. Le nombre de suites strictement croissantes {z_1\lt z_2\lt\cdots\lt z_{n-1}} de {\mathbb N} avec {z_k\lt2k} pour tout {k} (indication : {z_k=y_k+k-1}). Donner les solutions si {n=4}.
4. Le nombre de suites {d_1,d_2,\ldots,d_{n-1}} de {\mathbb N} telles que {d_{k+1}\leq d_k+1} pour tout indice admissible, en supposant que {d_1} est dans {\{0,1\}} (indication : {d_k=k-y_k}). Donner les solutions quand {n=4}.
5. Le nombre de façons d’écrire {n} paires de parenthèses pour que chaque parenthèse fermante corresponde à une parenthèse ouvrante. Par exemple, si {n=3}, il y a cinq possibilités : ((())), (()()), (())(), ()(()) et ()()().
6. Le nombre de chaînes de montagnes formées de {n} montées / et de {n} descentes \. La chaîne ne doit jamais descendre à une altitude inférieure à celle du point initial. On voit ici un exemple de chaîne avec {n=6}.
8. Soit {E} un ensemble muni d’un produit (celui de {a} par {b} est noté {ab}) non associatif. Une expression comme {abc} est donc dépourvue de sens tant qu’on ne choisit pas entre {(ab)c} et {a(bc)} : on dira que les deux expressions précédentes sont les parenthésages de {abc}.
Ainsi les parenthésages de {abcd} sont : {((ab)c)d}, {(ab)(cd)}, {(a(bc))d}, {a((bc)d)} et {a(b(cd))}.
On demande de montrer que le nombre de parenthésages de {a_1a_2\cdots a_{n+1}} est {C_n}.
9. Douze convives sont assis autour d’une table. De combien de manières ces douze personnes peuvent-elles échanger simultanément six poignées de mains sans que deux poignées différentes se croisent au-dessus de la table ? On voit ici l’une des solutions au problème.
