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}}.
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} un {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}}.
Ce dénombrement permet d’écrire :{\varphi_0(n)=2\varphi_0(n-1)+\varphi_1(n-1)}
Question I.2
Si {k\ge1}, exprimer de même {\varphi_k(n)} en fonction de {\varphi_k(n-1)}, {\varphi_{k+1}(n-1)} et {\varphi_{k-1}(n-1)}.
Question I.5
Pour {k\ge0,\,n\ge1}, soit {\psi_k(n)=\!\!\displaystyle\sum_{0\le j\le k}\!\dbinom{2n+1}{n-j}}
Montrer que les {\psi_k(n)} satisfont aux mêmes conditions que celles caractérisant les {\varphi_k(n)}.