Chemins sur une grille

Combien de chemins mènent d'un coin à l'autre d'un quadrillage en n'allant que vers la droite ou vers le haut ? Un chemin est un mot, leur nombre un coefficient binomial, et la grille se remplit comme le triangle de Pascal.

Sur un quadrillage de $n$ pas vers la droite et $p$ pas vers le haut, avec $n$ et $p$ de $1$ à $8$, on trace des chemins qui n'avancent que vers la droite ou vers le haut ; la page écrit le mot de chaque chemin et inscrit en chaque nœud le nombre de chemins qui y mènent. Pour $n = 4$ et $p = 3$, on lit $35$ au coin d'arrivée.

Ce que cela signifie : un chemin est un mot de $n + p$ lettres dont $n$ sont des pas vers la droite, et le choix des positions de ces $n$ lettres détermine le chemin. Il y a donc $\dbinom{n+p}{n} = \dfrac{(n+p)!}{n!\,p!}$ chemins. Le dernier pas d'un chemin qui arrive en un nœud vient de la gauche ou du dessous : le nombre inscrit en un nœud est la somme de ceux de ses deux voisins, ce qui est la relation de Pascal $\dbinom{i+j}{i} = \dbinom{i+j-1}{i-1} + \dbinom{i+j-1}{i}$.

Le piège le plus courant est de multiplier au lieu d'additionner, ou de compter les nœuds au lieu des pas : pour $n = 4$ et $p = 3$, la réponse n'est ni $4 \times 3 = 12$ ni $5 \times 4 = 20$, mais $\dbinom{7}{4} = 35$.