Un chemin est une suite de pas $(1,0)$ (vers la droite) ou $(0,1)$ (vers le haut). On considère les chemins de $O=(0,0)$ à $M=(6,4)$, et les points $P=(2,2)$ et $Q=(4,3)$.
- Combien y a-t-il de chemins de $O$ à $M$ ?
- Combien passent par $P$ ? par $Q$ ? par $P$ et par $Q$ ?
- Combien passent par $P$ ou par $Q$ ? Combien ne passent ni par $P$ ni par $Q$ ?
Un chemin de $(0,0)$ à $(a,b)$ est déterminé par les rangs de ses pas vers la droite.
Un chemin passant par $P$ se coupe en deux morceaux : avant $P$ et après $P$.
Le long d'un chemin, les deux coordonnées croissent : dans quel ordre rencontre-t-on $P$ et $Q$ ?
-
Un chemin de $(0,0)$ à $(a,b)$ compte $a+b$ pas dont $a$ vers la droite ; il est déterminé par l'ensemble des rangs des pas vers la droite, partie à $a$ éléments de $\llbracket1,a+b\rrbracket$. Il y a donc $\binom{a+b}{a}$ tels chemins, et ce nombre ne dépend que du déplacement $(a,b)$, pas du point de départ. De $O$ à $M$ : $\binom{10}{6}=\binom{10}{4}=210$.
-
Un chemin passant par $P$ se coupe de façon unique en un chemin de $O$ à $P$ suivi d'un chemin de $P$ à $M$, et tout tel couple donne un chemin passant par $P$ : c'est une bijection avec un produit cartésien. De $O$ à $P$ : $\binom42=6$ ; de $P$ à $M$ (déplacement $(4,2)$) : $\binom64=15$. Il y a donc $6\times15=90$ chemins par $P$.
De même, de $O$ à $Q$ : $\binom74=35$ ; de $Q$ à $M$ (déplacement $(2,1)$) : $\binom32=3$. Il y a $35\times3=105$ chemins par $Q$.
Les coordonnées croissent le long d'un chemin et $P$ a des coordonnées inférieures à celles de $Q$ : un chemin passant par $P$ et $Q$ passe d'abord par $P$. Il se découpe en trois morceaux : $O\to P$ ($6$), $P\to Q$ (déplacement $(2,1)$, $3$ chemins), $Q\to M$ ($3$). Il y en a $6\times3\times3=54$.
- En notant $\mathcal C_P$ et $\mathcal C_Q$ les ensembles de chemins passant par $P$ et par $Q$ : $$\operatorname{Card}(\mathcal C_P\cup\mathcal C_Q)=90+105-54=141.$$ Les chemins ne passant ni par $P$ ni par $Q$ sont au nombre de $210-141=69$.
$210$ ; $90$, $105$, $54$ ; $141$ et $69$