Déplacements dans ℤxℕ (1)

On considère le demi-plan ${\mathbb{Z}\times\mathbb{N}}$ des points à coordonnées entières, à ordonnées ${\ge0}$ .

Un robot part de ${(0,0)}$ et effectue des déplacements d’une unité, soit vers le haut (de ${(x,y)}$ à ${(x,y+1)}$ ) soit vers la droite (de ${(x,y)}$ à ${(x+1,y)}$ ) soit vers la gauche soit vers le bas.

On cherche le nombre ${\varphi(n)}$ de trajectoires formées de ${n}$ déplacements successifs (on dira ${n}$ -chemins) et qui se maintiennent dans le demi-plan ${\mathbb{Z}\times\mathbb{N}}$ .

${\fbox{Méthode I}}$ (voir la Méthode II)

Pour tout ${k\ge0}$ , et pour tout ${n\ge0}$ , on note ${\varphi_k(n)}$ le nombre de ${n}$ -chemins partant d’un point quelconque d’ordonnée ${k}$ et inclus dans ${\mathbb{Z}\times\mathbb{N}}$ .

Par convention ${\varphi_k(0)=1}$ .

L’objectif est donc de calculer ${\varphi(n)=\varphi_0(n)}$ .

Question I.1
Exprimer

{\varphi_0(n)}

en fonction de

{\begin{cases}\varphi_0(n-1)\\\varphi_1(n-1)\end{cases}}

Cliquer ici pour voir (ou cacher) la réponse

Soit

{\Gamma}

{n}

-chemin partant d’un point d’ordonnée

{0}

et contenu dans

{\mathbb{Z}\times\mathbb{N}}

Il y a ${\varphi_0(n)}$ façons de construire ${\Gamma}$ .

De trois choses l’une :

Ou bien ${\Gamma}$ débute par un mouvement à droite.

On se retrouve alors à nouveau en un point d’ordonnée ${0}$ .

Il y a donc ${\varphi_0(n-1)}$ façons de compléter ${\Gamma}$ par un ${(n-1)}$ -chemin inclus dans ${\mathbb{Z}\times\mathbb{N}}$ .
Ou bien ${\Gamma}$ débute par un mouvement à gauche.

Il y a encore ${\varphi_0(n-1)}$ façons de compléter ${\Gamma}$ .
Ou bien ${\Gamma}$ débute vers le haut.

On se retrouve alors en un point d’ordonnée ${1}$ .

Il y a alors ${\varphi_1(n-1)}$ façons de compléter ${\Gamma}$ par un ${(n-1)}$ -chemin inclus dans ${\mathbb{Z}\times\mathbb{N}}$ .