Chemins sur une grille

Application directe du cours · niveau 3 (difficile) · mathématiques (PTSI), chapitre 15 — Dénombrement · D. Problèmes et doubles comptages

Énoncé

Combien de chemins mènent de $(0, 0)$ à $(p, q)$ en ne faisant que des pas vers la droite (D) ou vers le haut (H) ?

Corrigé

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}$ :

$(p p + q) chemins.$

Exemple : de $(0, 0)$ à $(4, 3)$ , $(4 7) = 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.)

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.