Compter les chemins — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 5)

Compter les chemins

Chemins de valeur optimale · niveau 2

Énoncé

On note $N (l, c)$ le nombre de chemins de $(0, 0)$ à $(l, c)$ avec les déplacements N, E et NE.

Établir la récurrence des valeurs $N (l, c)$ et calculer le tableau pour une grille $5 \times 5$ . (Ce sont les nombres de Delannoy.)
Montrer que $N (n, n) \geq 2^{n}$ . Que vaut $N (20, 20)$ ? Conclure sur l'énumération exhaustive.
Même question sans le déplacement NE ; reconnaître les coefficients binomiaux.

Un chemin vers $(l, c)$ arrive par un dernier pas N, E ou NE ; les trois cas sont disjoints.

Base. $N (l, 0) = N (0, c) = 1$ (un seul chemin, tout droit).

Hérédité. $\forall l \geq 1$ , $\forall c \geq 1$ : $N (l, c) = N (l - 1, c) + N (l, c - 1) + N (l - 1, c - 1)$ .


Avec NE :
  [1, 9, 41, 129, 321]
  [1, 7, 25, 63, 129]
  [1, 5, 13, 25, 41]
  [1, 3, 5, 7, 9]
  [1, 1, 1, 1, 1]

Découpons un chemin de $(0, 0)$ à $(n, n)$ en $n$ étapes qui avancent chacune d'une ligne et d'une colonne : chaque étape peut se faire par un pas NE, ou par les deux pas N puis E. Ces $2^{n}$ chemins sont distincts, donc $N (n, n) \geq 2^{n}$ . Le programme donne $N (20, 20) = 260543813797441$ : l'énumération des chemins d'une grille $21 \times 21$ est déjà hors de portée, alors que la programmation dynamique calcule le meilleur en $441$ étapes.
Sans NE, $N (l, c) = N (l - 1, c) + N (l, c - 1)$ : c'est la relation de Pascal, et $N (l, c) = (l l + c)$ (choisir les $l$ pas N parmi les $l + c$ pas). Par exemple $N (4, 4) = (4 8) = 70$ .


Sans NE :
  [1, 5, 15, 35, 70]
  [1, 4, 10, 20, 35]
  [1, 3, 6, 10, 15]
  [1, 2, 3, 4, 5]
  [1, 1, 1, 1, 1]