38
CHAPITRE 4 : PROBABILIT ´
ES DISCR `
ETES. D ´
ENOMBREMENTS
pour d´ emontrer la formule
ϕ(n)
n
=
p | n
1 −
1
p
,
o` u le produit au second membre est ´ etendu `
a tous les facteurs premiers p
de n qui divisent n. En effet, on a, d’apr` es la formule de Poincar´ e :
|A 1 ∪ · · · ∪ A r | =
i
|A i | −
i
r−1
|A 1 ∩ · · · ∩ A r | .
Or |A 1 ∪ · · · ∪ A r | = n − ϕ(n) ; d’autre part, si d | n, alors le nombre d’entiers
de Ω qui sont divisibles par d est n/d. On a donc : |A i | = n/p i , |A i ∩ A j | =
n/(p i p j ), . . . , |A i ∩ · · · ∩ A r | = n/(p 1 . . . p r ). La formule de Poincar´ e s’´ ecrit
donc :
n − ϕ(n) =
i
n
p i
−
i
p i p j
+ · · · + (−1)
r−1
n
p 1 . . . p r
;
ϕ(n)
n
= 1 −
i
1
p i
+
i
p i p j
+ · · · + (−1)
r
1
p 1 . . . p r
=
p | n
1 −
1
p
.
2. Le probl` eme des rencontres. — Une urne contient n boules num´ erot´ ees
de 1 ` a n. On les extrait successivement sans remise et apr` es chaque tirage,
on observe le num´ ero de la boule tir´ ee. On d´ ecrit cette exp´ erience au moyen
du triplet (Ω, A, P), o` u Ω est l’ensemble des permutations de {1, . . . , n}, o` u
A est P(Ω) et o` u P est l’´ equir´ epartition.
On dit qu’il y a rencontre au i
i` eme tirage, si la boule tir´ ee porte le num´ ero i
et l’on d´ esigne par E i l’´ ev` enement il y a rencontre au i
i` eme tirage ; E i
est la partie de Ω dont les ´ el´ ements sont les permutations de {1, . . . , n}
dont la i
i` eme place est occup´ ee par le num´ ero i. De mˆ eme, si (i 1 , . . . , i k ) est
une suite strictement croissante d’entiers compris entre 1 et n, l’intersection
E i 1 ∩ · · · ∩ E i k est la partie de Ω dont les ´ el´ ements sont les permutations
dont les i 1
i` eme , . . . , i k
i` eme places sont occup´ ees par les num´ eros i 1 , . . . , i k .
On a donc, en vertu de l’´ equir´ epartition : P(E i ) = (n − 1)!/n! (i = 1, . . . , n) ;
P(E i 1 ∩ E i 2 ) = (n − 2)!/n! (1 ≤ i 1 < i 2 ≤ n) ; P(E 1 ∩ · · · ∩ E n ) = 1/n!.
a) Soit A l’´ ev` enement il y a au moins une rencontre , c’est-` a-dire
A = E 1 ∪ · · · ∪ E n . La formule de Poincar´ e donne :
P(A) =
n
k=1
(−1)
k−1
1≤i 1 <··· P(E i 1 ∩ · · · ∩ E i k )
=
n
k=1
(−1)
k−1
n
k
(n − k)!
n!
=
n
k=1
(−1)
k−1
k!
.
CHAPITRE 4 : PROBABILIT ´
ES DISCR `
ETES. D ´
ENOMBREMENTS
pour d´ emontrer la formule
ϕ(n)
n
=
p | n
1 −
1
p
,
o` u le produit au second membre est ´ etendu `
a tous les facteurs premiers p
de n qui divisent n. En effet, on a, d’apr` es la formule de Poincar´ e :
|A 1 ∪ · · · ∪ A r | =
i
|A i | −
i
r−1
|A 1 ∩ · · · ∩ A r | .
Or |A 1 ∪ · · · ∪ A r | = n − ϕ(n) ; d’autre part, si d | n, alors le nombre d’entiers
de Ω qui sont divisibles par d est n/d. On a donc : |A i | = n/p i , |A i ∩ A j | =
n/(p i p j ), . . . , |A i ∩ · · · ∩ A r | = n/(p 1 . . . p r ). La formule de Poincar´ e s’´ ecrit
donc :
n − ϕ(n) =
i
n
p i
−
i
p i p j
+ · · · + (−1)
r−1
n
p 1 . . . p r
;
ϕ(n)
n
= 1 −
i
1
p i
+
i
p i p j
+ · · · + (−1)
r
1
p 1 . . . p r
=
p | n
1 −
1
p
.
2. Le probl` eme des rencontres. — Une urne contient n boules num´ erot´ ees
de 1 ` a n. On les extrait successivement sans remise et apr` es chaque tirage,
on observe le num´ ero de la boule tir´ ee. On d´ ecrit cette exp´ erience au moyen
du triplet (Ω, A, P), o` u Ω est l’ensemble des permutations de {1, . . . , n}, o` u
A est P(Ω) et o` u P est l’´ equir´ epartition.
On dit qu’il y a rencontre au i
i` eme tirage, si la boule tir´ ee porte le num´ ero i
et l’on d´ esigne par E i l’´ ev` enement il y a rencontre au i
i` eme tirage ; E i
est la partie de Ω dont les ´ el´ ements sont les permutations de {1, . . . , n}
dont la i
i` eme place est occup´ ee par le num´ ero i. De mˆ eme, si (i 1 , . . . , i k ) est
une suite strictement croissante d’entiers compris entre 1 et n, l’intersection
E i 1 ∩ · · · ∩ E i k est la partie de Ω dont les ´ el´ ements sont les permutations
dont les i 1
i` eme , . . . , i k
i` eme places sont occup´ ees par les num´ eros i 1 , . . . , i k .
On a donc, en vertu de l’´ equir´ epartition : P(E i ) = (n − 1)!/n! (i = 1, . . . , n) ;
P(E i 1 ∩ E i 2 ) = (n − 2)!/n! (1 ≤ i 1 < i 2 ≤ n) ; P(E 1 ∩ · · · ∩ E n ) = 1/n!.
a) Soit A l’´ ev` enement il y a au moins une rencontre , c’est-` a-dire
A = E 1 ∪ · · · ∪ E n . La formule de Poincar´ e donne :
P(A) =
n
k=1
(−1)
k−1
1≤i 1 <··· P(E i 1 ∩ · · · ∩ E i k )
=
n
k=1
(−1)
k−1
n
k
(n − k)!
n!
=
n
k=1
(−1)
k−1
k!
.