Déplacements dans ℤxℕ (2)

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 II}} (voir la Méthode I)

Un {n}-chemin partant de {(0,0)} peut être représenté par une chaîne de {n} caractères égaux à {D} (droite), à {H} (haut), à {G} (gauche) ou à {B} (bas).

On transforme tout {n}-chemin de la manière suivante : on remplace simultanément chaque {G} par {GD}, chaque {D} par {DG}, chaque {H} par {DD}, chaque {B} par {GG}. Ensuite on préfixe la chaîne obtenue par la lettre {D}.

Question II.1

Montrer qu’on obtient ainsi un {(2n\!+\!1)}-chemin inclus dans {\mathbb{N}} et partant de {0} (les seuls déplacements possibles étant {G} et {D}, le premier étant bien sûr {D}).

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 II.2
Montrer que la transformation précédente est réversible, et que donc {\varphi(n)} est le nombre de {(2n\!+\!1)}-chemins partant de {0} et inclus dans {\mathbb{N}}.
Indication : on sera amené à retrancher du nombre de {(2n\!+\!1)}-chemins partant de {0} et à destination finale dans {\mathbb{N}} le nombre de ceux qui passent par {-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 II.3
Montrer que tout {(2n\!+\!1)}-chemin de {\mathbb{Z}} partant de {0} et à destination finale dans {\mathbb{N}} se termine en {2n\!+\!1\!-\!2k} avec {0\le k\le n}.
Pour {k} fixé, montrer que leur nombre est {\dbinom{2n\!+\!1}{k}}.
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 II.4
Soit {\Gamma} un {(2n\!+\!1)}-chemin de {\mathbb{Z}} allant de {0} à {2n\!+\!1\!-\!2k\ge0} mais passant par {-1}.

On inverse simultanément les déplacements de {\Gamma} de {0} jusqu’au 1er passage en {-1}.

Montrer qu’on obtient ainsi un {(2n\!+\!1)}-chemin {\Gamma'} de {\mathbb{Z}} allant de {0} à {2n\!+\!3\!-\!2k}.

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 II.5
Montrer que la transformation précédente est réversible. En déduire le nombre de {(2n\!+\!1)}-chemins de {\mathbb{Z}} allant de {0} à {2n+1-2k\ge0} mais passant par {-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 II.6
Montrer en définitive que le nombre de {(2n\!+\!1)}-chemins qui partent de {0} et qui sont inclus dans {\mathbb{N}} est égal à :{\displaystyle\sum_{k=0}^{n}\biggl(\dbinom{2n+1}{k}-\dbinom{2n+1}{k-1}\biggr)=\dbinom{2n+1}{n}}et conclure.
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).