Chemins sur un quadrillage
Dans un repère du plan, un pion part du point et doit atteindre le point . À chaque pas, il avance d'une unité, soit vers la droite (pas ), soit vers le haut (pas ). On appelle chemin la suite des pas qui mène de à . On note l'ensemble des chemins.
Repère avec quadrillage, gradué de 1 en 1, de 0 à 6 sur l'axe horizontal et de 0 à 4 sur l'axe vertical. Le pion part de l'origine O, en bas à gauche, et doit atteindre A, en haut à droite, six unités plus à droite et quatre plus haut. Le point B est près du départ, deux unités à droite et une au-dessus de O. Le point K est près de l'arrivée, deux unités à gauche de A et une en dessous. Les points A, B et K sont écrits avec leurs deux nombres.
- 1.0,5pts
Justifier qu'un chemin compte exactement pas, dont pas et pas .
- 2.
On note l'ensemble des parties à éléments de . À un chemin , on associe l'ensemble des rangs de ses pas . Par exemple, le chemin donne . Montrer que est une bijection de sur .
1ptsQuadrillage gradué de 1 en 1. Une ligne brisée faite de dix flèches d'une unité part de O et arrive en A. Dans l'ordre : une flèche vers le haut, deux vers la droite, une vers le haut, deux vers la droite, une vers le haut, deux vers la droite, une dernière vers le haut. Les montées sont les pas de rangs 1, 4, 7 et 10. Le chemin passe par les nœuds d'abscisse 2 et d'ordonnée 1, puis d'abscisse 4 et d'ordonnée 3.
Le chemin HDDHDDHDDH tracé pas à pas : quatre montées et six pas vers la droite mènent de O à A. - 3.0,5pts
En déduire le nombre de chemins.
- 4.1pts
Dénombrer les chemins qui passent par le point .
- 5.0,5pts
En déduire le nombre de chemins qui évitent le point .
- 6.1,5pts
Dénombrer les chemins qui passent par ou par le point .

Outil : suis l'abscisse et l'ordonnée du pion. Début : seul un pas modifie l'abscisse.
Outil : une réciproque explicite. Début : à une partie de , associe la suite de pas dont le pas de rang est si . Point délicat : vérifie que cette suite est bien un chemin, puis les deux composées.
Outil : le résultat « cardinal et bijection », puis le nombre de combinaisons.
Outil : le principe multiplicatif. Début : découpe un tel chemin en un trajet de à , puis un trajet de à . Point délicat : compte les pas de chaque trajet comme en 1. et 2.
Outil : le complémentaire dans .
Outil : le cardinal d'une réunion de deux parties qui se chevauchent. Début : compte les chemins par comme en 4. Point délicat : un chemin qui passe par et par se découpe en trois trajets.
L'abscisse du pion augmente de à chaque pas et ne change pas lors d'un pas . Elle passe de à : un chemin compte exactement pas . De même, l'ordonnée passe de à : un chemin compte exactement pas . Il a donc pas.
arrive dans . D'après 1., un chemin a pas dont pas , à des rangs distincts : est une partie à éléments de .
Une réciproque. Soit . Notons la suite de pas dont le pas de rang est si , et sinon. Elle compte pas et pas : partie de , elle mène en . Donc .
Les deux composées. Les rangs des pas de sont exactement les éléments de : . Un chemin est déterminé par les rangs de ses pas , les autres pas étant : .
Conclusion. est bijective, de réciproque .
D'après 2. et le résultat « cardinal et bijection », . Or Il y a chemins.
La somme des coordonnées du pion augmente de à chaque pas : le pion ne peut être en qu'après pas. Un chemin passant par se découpe donc, d'une seule façon, en deux trajets.
- De à : pas, dont pas . Un tel trajet est déterminé par le rang de son unique pas : par une bijection analogue à celle de 2., il y a trajets.
- De à : pas et pas , soit pas. Un tel trajet est déterminé par les rangs de ses pas : de même, il y a trajets, quel que soit le premier.
D'après le principe multiplicatif, chemins passent par .
Les chemins qui évitent forment le complémentaire, dans , de l'ensemble des chemins passant par . D'après la formule du complémentaire, il y en a .
Notons et les ensembles des chemins passant par et par .
Par . Comme en 4., le pion ne peut être en qu'après pas. De à : pas dont pas ; un tel trajet est déterminé par les rangs de ses pas , donc, par une bijection analogue à celle de 2., il y a trajets. De à : pas et pas ; de même, trajets. D'après le principe multiplicatif, .
Par et . Le pion passe en après pas et en après pas. On compte trajets de à , puis, de la même façon, trajets de à ( pas , pas ), puis trajets de à . Ainsi .
Réunion. .
