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} 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)}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question I.3
Montrer que les relations obtenues déterminent les {\varphi_k(n)} de façon unique.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question I.4
Préciser {\varphi_0(1)} et {\varphi_k(n)} pour {k\ge n}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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)}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question I.6
Déduire de ce qui précède que {\varphi(n)=\dbinom{2n+1}{n}}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).