Chemins dans une grille et nombres de Catalan

Solution

1. 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}$.
2. 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}$.
3. 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).