36
CHAPITRE 4 : PROBABILIT ´
ES DISCR `
ETES. D ´
ENOMBREMENTS
Par cons´ equent, le nombre de chemins allant de (0, 0) `
a (n, s) est ´ egal ` a :
(5.3)
c n,s =
p + q
q
=
p + q
p
avec p =
n + s
2
.
On pose c n,s = 0, lorsque n + s et n − s ne sont pas tous deux pairs.
Soit A et B deux points du plan de coordonn´ ees A = (a, α) et B = (b, β).
On suppose 0 ≤ a < b, α ≥ 1, β ≥ 1. Ces hypoth` eses ´ etant satisfaites, on a
le lemme suivant, dit du principe de r´ eflexion.
Lemme 5.1. — Le nombre de chemins de C allant de A ` a B, qui touchent
ou traversent l’axe horizontal est ´ egal au nombre de chemins allant du point
A
= (a, −α) ` a B.
A •
A
•
a
T
B
•
b
d
d
d
d
d
d
d d
d
d
d
d d
d d
d
d
d
Fig. 2
D´ emonstration. — La d´ emonstration est de nature purement g´ eom´ etrique
(cf. Fig. 2). Soit ω un chemin touchant ou traversant l’axe horizontal. On
d´ esigne par T le point le plus `
a gauche o` u ω atteint l’axe horizontal. Soit ω 1
la portion du chemin ω allant de A ` a T et ω 2 la portion allant de T ` a B.
On forme un nouveau chemin allant de A
` a B en prenant le sym´ etrique de
ω 1 par rapport `
a l’axe horizontal et en lui adjoignant ω 2 . Soit ω
ce nouveau
chemin. Il est clair que ω → ω
est une bijection envoyant la premi` ere famille
des chemins sur la seconde.
Analytiquement, le point T est le point d’abscisse t d´ efini par
s a > 0, s a+1 > 0, . . . , s t−1 > 0, s t = 0,
et le nouveau chemin est d´ efini par la s´ equence :
−s a , −s a+1 , . . . , −s t−1 , s t , s t+1 , . . . , s b .
La plus c´ el` ebre application du principe de r´ eflexion est le th´ eor` eme du
scrutin. Avant de l’´ etablir, donnons encore un lemme de comptage, dans
lequel on conserve les notations de (5.1), (5.2) et (5.3).
CHAPITRE 4 : PROBABILIT ´
ES DISCR `
ETES. D ´
ENOMBREMENTS
Par cons´ equent, le nombre de chemins allant de (0, 0) `
a (n, s) est ´ egal ` a :
(5.3)
c n,s =
p + q
q
=
p + q
p
avec p =
n + s
2
.
On pose c n,s = 0, lorsque n + s et n − s ne sont pas tous deux pairs.
Soit A et B deux points du plan de coordonn´ ees A = (a, α) et B = (b, β).
On suppose 0 ≤ a < b, α ≥ 1, β ≥ 1. Ces hypoth` eses ´ etant satisfaites, on a
le lemme suivant, dit du principe de r´ eflexion.
Lemme 5.1. — Le nombre de chemins de C allant de A ` a B, qui touchent
ou traversent l’axe horizontal est ´ egal au nombre de chemins allant du point
A
= (a, −α) ` a B.
A •
A
•
a
T
B
•
b
d
d
d
d
d
d
d d
d
d
d
d d
d d
d
d
d
Fig. 2
D´ emonstration. — La d´ emonstration est de nature purement g´ eom´ etrique
(cf. Fig. 2). Soit ω un chemin touchant ou traversant l’axe horizontal. On
d´ esigne par T le point le plus `
a gauche o` u ω atteint l’axe horizontal. Soit ω 1
la portion du chemin ω allant de A ` a T et ω 2 la portion allant de T ` a B.
On forme un nouveau chemin allant de A
` a B en prenant le sym´ etrique de
ω 1 par rapport `
a l’axe horizontal et en lui adjoignant ω 2 . Soit ω
ce nouveau
chemin. Il est clair que ω → ω
est une bijection envoyant la premi` ere famille
des chemins sur la seconde.
Analytiquement, le point T est le point d’abscisse t d´ efini par
s a > 0, s a+1 > 0, . . . , s t−1 > 0, s t = 0,
et le nouveau chemin est d´ efini par la s´ equence :
−s a , −s a+1 , . . . , −s t−1 , s t , s t+1 , . . . , s b .
La plus c´ el` ebre application du principe de r´ eflexion est le th´ eor` eme du
scrutin. Avant de l’´ etablir, donnons encore un lemme de comptage, dans
lequel on conserve les notations de (5.1), (5.2) et (5.3).