COMPL ´
EMENTS ET EXERCICES
37
Lemme 5.2. — Soient n ≥ 1 et s ≥ 1. Le nombre de chemins allant de
(0, 0) ` a (n, s) et restant toujours strictement au-dessus de l’axe horizontal est
´ egal `
a
s
n
c n,s =
p − q
p + q
p + q
p
.
D´ emonstration. — Si un chemin ω partant de (0, 0) reste toujours audessus de l’axe horizontal, il satisfait n´ ecessairement s 1 = 1. De l` a, le nombre
de tels chemins est aussi ´ egal au nombre de chemins allant de (1, 1) `
a (n, s),
ne touchant, ni traversant l’axe horizontal. D’apr` es le pr´ ec´ edent lemme et la
formule (5.3), ce nombre est ´ egal ` a :
c n−1,s−1 − c n−1,s+1 =
p + q − 1
p − 1
−
p + q − 1
p
=
p
p + q
−
q
p + q
p + q
p
=
p − q
p + q
p + q
p
=
s
n
c n,s .
Th´ eor` eme 5.3 (du scrutin). — Dans un scrutin, il y a p bulletins pour
le candidat P et q pour le candidat Q. On suppose p > q. Alors la probabilit´ e
pour que, durant tout le d´ epouillement, P soit toujours en tˆ ete est ´ egale `
a
(p − q)/(p + q).
D´ emonstration. — Le probl` eme revient ` a probabiliser l’ensemble de tous
les chemins allant de (0, 0) `
a (p + q, p − q). Un tel chemin repr´ esente, en
effet, un d´ epouillement (+1 si le vote est pour P, −1 si le vote est pour Q).
En prenant l’´ equir´ epartition sur l’ensemble de ces chemins, il s’agit d’´ evaluer
le nombre des chemins qui restent toujours strictement au-dessus de l’axe
horizontal. C’est ce qui a ´ et´ e fait au lemme pr´ ec´ edent.
COMPL ´
EMENTS ET EXERCICES
1. Une application de la formule de Poincar´ e. — Soit n ≥ 2 et n =
p
α 1
1 . . . p
α r
r sa d´ ecomposition en facteurs premiers. Prenons Ω = {1, 2, . . . , n}
et notons A k la partie de Ω constitu´ ee par les entiers divisibles par le nombre
premier p k (k = 1, . . . , r). La r´ eunion A 1 ∪ · · · ∪ A r est la partie de Ω
constitu´ ee par les entiers qui sont divisibles par l’un au moins des premiers
p 1 , . . . , p r et (A 1 ∪ · · · ∪ A r )
c est la partie de Ω constitu´ ee par les entiers
qui ne sont divisibles par aucun des nombres premiers p 1 , . . . , p r , c’est-` adire qui sont premiers avec n. Son cardinal est not´ e ϕ(n). La fonction ϕ est
appel´ ee la fonction arithm´ etique d’Euler. On utilise la formule de Poincar´ e
EMENTS ET EXERCICES
37
Lemme 5.2. — Soient n ≥ 1 et s ≥ 1. Le nombre de chemins allant de
(0, 0) ` a (n, s) et restant toujours strictement au-dessus de l’axe horizontal est
´ egal `
a
s
n
c n,s =
p − q
p + q
p + q
p
.
D´ emonstration. — Si un chemin ω partant de (0, 0) reste toujours audessus de l’axe horizontal, il satisfait n´ ecessairement s 1 = 1. De l` a, le nombre
de tels chemins est aussi ´ egal au nombre de chemins allant de (1, 1) `
a (n, s),
ne touchant, ni traversant l’axe horizontal. D’apr` es le pr´ ec´ edent lemme et la
formule (5.3), ce nombre est ´ egal ` a :
c n−1,s−1 − c n−1,s+1 =
p + q − 1
p − 1
−
p + q − 1
p
=
p
p + q
−
q
p + q
p + q
p
=
p − q
p + q
p + q
p
=
s
n
c n,s .
Th´ eor` eme 5.3 (du scrutin). — Dans un scrutin, il y a p bulletins pour
le candidat P et q pour le candidat Q. On suppose p > q. Alors la probabilit´ e
pour que, durant tout le d´ epouillement, P soit toujours en tˆ ete est ´ egale `
a
(p − q)/(p + q).
D´ emonstration. — Le probl` eme revient ` a probabiliser l’ensemble de tous
les chemins allant de (0, 0) `
a (p + q, p − q). Un tel chemin repr´ esente, en
effet, un d´ epouillement (+1 si le vote est pour P, −1 si le vote est pour Q).
En prenant l’´ equir´ epartition sur l’ensemble de ces chemins, il s’agit d’´ evaluer
le nombre des chemins qui restent toujours strictement au-dessus de l’axe
horizontal. C’est ce qui a ´ et´ e fait au lemme pr´ ec´ edent.
COMPL ´
EMENTS ET EXERCICES
1. Une application de la formule de Poincar´ e. — Soit n ≥ 2 et n =
p
α 1
1 . . . p
α r
r sa d´ ecomposition en facteurs premiers. Prenons Ω = {1, 2, . . . , n}
et notons A k la partie de Ω constitu´ ee par les entiers divisibles par le nombre
premier p k (k = 1, . . . , r). La r´ eunion A 1 ∪ · · · ∪ A r est la partie de Ω
constitu´ ee par les entiers qui sont divisibles par l’un au moins des premiers
p 1 , . . . , p r et (A 1 ∪ · · · ∪ A r )
c est la partie de Ω constitu´ ee par les entiers
qui ne sont divisibles par aucun des nombres premiers p 1 , . . . , p r , c’est-` adire qui sont premiers avec n. Son cardinal est not´ e ϕ(n). La fonction ϕ est
appel´ ee la fonction arithm´ etique d’Euler. On utilise la formule de Poincar´ e