On considère une grille $n \times n$. Un chemin monotone va de $(0,0)$ à $(n,n)$ en n'effectuant que des pas vers la droite $(+1, 0)$ ou vers le haut $(0, +1)$.
Combien y a-t-il de chemins monotones de $(0,0)$ à $(n,n)$ ?
Combien de ces chemins ne passent jamais au-dessus de la diagonale $y = x$ (c'est-à-dire toujours $y \le x$ pour les coordonnées parcourues) ?
Calculer ce nombre pour $n = 3$.
Solution
Total des chemins :
Un chemin monotone consiste en $n$ pas à droite et $n$ pas en haut, soit $2n$ pas en tout.
Nombre de chemins $= \binom{2n}{n}$.
Chemins sous la diagonale (Nombres de Catalan) :
On cherche les chemins avec $y \le x$ à tout moment (au sens : on a fait au moins autant de pas à droite que vers le haut). Méthode de réflexion de Lindström-Gessel-Viennot : Les chemins "mauvais" (qui franchissent $y = x+1$) sont en bijection avec les chemins de $(-1, 1)$ à $(n,n)$ (en réfléchissant la partie initiale par rapport à $y = x+1$).
Nombre de mauvais chemins $= \binom{2n}{n-1}$.
Nombre de chemins de Catalan $= C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1}\binom{2n}{n}$.
Pour $n = 3$ :
$C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \times 20 = 5$.
Les 5 chemins sont : RRRHH, RRHRRH... (on peut les énumérer explicitement).