28
CHAPITRE 4 : PROBABILIT ´
ES DISCR `
ETES. D ´
ENOMBREMENTS
Soient n ≥ 2 et A 1 , A 2 , . . . , A n des ensembles quelconques, ´ eventuellement
vides, mais finis. Alors
|A 1 ∪ · · · ∪ A n | =
i
|A i | −
i
n−1
|A 1 ∩ · · · ∩ A n | ,
ou bien
(3.4)
|A 1 ∪ · · · ∪ A n | =
n
k=1
(−1)
k−1
1≤i 1 <··· |A i 1 ∩ · · · ∩ A i k | .
Remarque. — Soient A et B deux ensembles finis de cardinal n et p,
respectivement. La formule de la somme peut ˆ etre reformul´ ee de fa¸ con
intuitive en une r` egle de la somme : si un objet a peut ˆ etre choisi de n
fa¸ cons et un objet b de p autres fa¸ cons, il y a (n + p) fa¸ cons de choisir soit a,
soit b .
Cet ´ enonc´ e conserve une l´ eg` ere ambigu¨ ıt´ e et c’est justement le langage de
la th´ eorie des ensembles qui permet de lever celle-ci. Dans la formule suivante,
on voit apparaˆ ıtre le produit cart´ esien A×B constitu´ e par l’ensemble de tous
les couples (a, b) o` u a (resp. b) appartient `
a A (resp. `
a B).
Proposition 3.4 (formule du produit). — Si A et B sont deux ensembles
finis (non n´ ecessairement disjoints), alors le produit cart´ esien A × B est fini
et l’on a :
(3.5)
|A × B| = |A| · |B| .
D´ emonstration. — En conservant les mˆ emes notations que dans la Proposition 3.3, on construit une bijection θ de [ np ] = {1, 2, . . . , np} sur A × B de
la fa¸ con suivante. D’abord [ np ] =
1≤k≤p [ n(k − 1) + 1, nk ]. Il existe ensuite
une bijection de [ n(k − 1) + 1, nk ] sur [ n ] et une bijection de [ n ] sur le
sous-ensemble A k = {(ϕ(1), ψ(k)), (ϕ(2), ψ(k)), . . . , (ϕ(n), ψ(k))} de A × B.
Soit θ k le produit de composition de ces deux bijections (1 ≤ k ≤ p). Comme
les ensembles A k sont disjoints deux `
a deux et de r´ eunion A × B, on d´ efinit
θ comme ´ etant l’application dont la restriction `
a [ n(k − 1) + 1, nk ] est θ k .
La formule (3.2) donne alors :
|A × B| = |A 1 | + · · · + |A p | = np = |A| · |B| .
Remarque. — De mˆ eme, la r` egle du produit s’´ enonce : si un objet a peut
ˆ etre choisi de n fa¸ cons et qu’ensuite l’objet b peut ˆ etre choisi de p fa¸ cons, la
paire (a, b), prise dans cet ordre, peut ˆ etre choisie de np fa¸ cons .
La formule du produit se prolonge au cas de n (n ≥ 2) ensembles finis. On
obtient pour toute suite B 1 , B 2 , . . . , B n d’ensembles finis la formule :
(3.7)
|B 1 × B 2 × · · · × B n | = |B 1 | × |B 2 | × · · · × |B n | .
Autrement dit, si B i a pour cardinal p i pour i = 1, 2, . . . , n, le nombre de
suites ordonn´ ees (b 1 , b 2 , . . . , b n ), o` u chaque b i appartient `
a B i (i = 1, 2, . . . , n)
est ´ egal ` a p 1 p 2 · · · p n .
CHAPITRE 4 : PROBABILIT ´
ES DISCR `
ETES. D ´
ENOMBREMENTS
Soient n ≥ 2 et A 1 , A 2 , . . . , A n des ensembles quelconques, ´ eventuellement
vides, mais finis. Alors
|A 1 ∪ · · · ∪ A n | =
i
|A i | −
i
n−1
|A 1 ∩ · · · ∩ A n | ,
ou bien
(3.4)
|A 1 ∪ · · · ∪ A n | =
n
k=1
(−1)
k−1
1≤i 1 <··· |A i 1 ∩ · · · ∩ A i k | .
Remarque. — Soient A et B deux ensembles finis de cardinal n et p,
respectivement. La formule de la somme peut ˆ etre reformul´ ee de fa¸ con
intuitive en une r` egle de la somme : si un objet a peut ˆ etre choisi de n
fa¸ cons et un objet b de p autres fa¸ cons, il y a (n + p) fa¸ cons de choisir soit a,
soit b .
Cet ´ enonc´ e conserve une l´ eg` ere ambigu¨ ıt´ e et c’est justement le langage de
la th´ eorie des ensembles qui permet de lever celle-ci. Dans la formule suivante,
on voit apparaˆ ıtre le produit cart´ esien A×B constitu´ e par l’ensemble de tous
les couples (a, b) o` u a (resp. b) appartient `
a A (resp. `
a B).
Proposition 3.4 (formule du produit). — Si A et B sont deux ensembles
finis (non n´ ecessairement disjoints), alors le produit cart´ esien A × B est fini
et l’on a :
(3.5)
|A × B| = |A| · |B| .
D´ emonstration. — En conservant les mˆ emes notations que dans la Proposition 3.3, on construit une bijection θ de [ np ] = {1, 2, . . . , np} sur A × B de
la fa¸ con suivante. D’abord [ np ] =
1≤k≤p [ n(k − 1) + 1, nk ]. Il existe ensuite
une bijection de [ n(k − 1) + 1, nk ] sur [ n ] et une bijection de [ n ] sur le
sous-ensemble A k = {(ϕ(1), ψ(k)), (ϕ(2), ψ(k)), . . . , (ϕ(n), ψ(k))} de A × B.
Soit θ k le produit de composition de ces deux bijections (1 ≤ k ≤ p). Comme
les ensembles A k sont disjoints deux `
a deux et de r´ eunion A × B, on d´ efinit
θ comme ´ etant l’application dont la restriction `
a [ n(k − 1) + 1, nk ] est θ k .
La formule (3.2) donne alors :
|A × B| = |A 1 | + · · · + |A p | = np = |A| · |B| .
Remarque. — De mˆ eme, la r` egle du produit s’´ enonce : si un objet a peut
ˆ etre choisi de n fa¸ cons et qu’ensuite l’objet b peut ˆ etre choisi de p fa¸ cons, la
paire (a, b), prise dans cet ordre, peut ˆ etre choisie de np fa¸ cons .
La formule du produit se prolonge au cas de n (n ≥ 2) ensembles finis. On
obtient pour toute suite B 1 , B 2 , . . . , B n d’ensembles finis la formule :
(3.7)
|B 1 × B 2 × · · · × B n | = |B 1 | × |B 2 | × · · · × |B n | .
Autrement dit, si B i a pour cardinal p i pour i = 1, 2, . . . , n, le nombre de
suites ordonn´ ees (b 1 , b 2 , . . . , b n ), o` u chaque b i appartient `
a B i (i = 1, 2, . . . , n)
est ´ egal ` a p 1 p 2 · · · p n .