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}). |
| 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}. |
| 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}}. |
| 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}. |
| 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}. |
| 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. |