Chemins sur une grille

Un tel chemin comporte exactement $p$ pas D et $q$ pas H, soit $p+q$ pas en tout : il est entièrement déterminé par le choix des positions des pas D dans la suite des $p+q$ pas — une partie à $p$ éléments de $\{1,\dots ,p+q\}$ :

$$\boxed{\left(\genfrac{}{}{0ex}{}{p+q}{p}\right)}\text{chemins.}$$

Exemple : de $(0,0)$ à $(4,3)$, $\left(\genfrac{}{}{0ex}{}{7}{4}\right)=35$ chemins.

(Compter des chemins en comptant des mots : l'encodage est l'arme secrète du dénombrement. Ainsi, de $(0,0)$ à $(4,3)$, le chemin droite-droite-haut-droite-haut-droite-haut est le mot DDHDHDH, et réciproquement.)