COURS 9
Nombresentiers naturels –Combinatoire
EXEMPLE
De combien de façons dix convives
peuvent-ils se placer autour d’une
table? 10! = 3628 800.
Une bijection de E dans E est appelée permutation des éléments de E. On
utilisel es permutations dans tous les problèmes de choix d’un ordre de tous les
éléments d’un ensemble fini.
3.7 • Partiesd’un ensemble fini
Théorème 9
Si E estunensemble fini de cardinal n,
Card P(E) = 2
n
Démonstration
Effectuons une récurrence sur n.
Pour n = 0, E = ∅ et P(E) = {∅} ;C ard P(E) = 1 = 2
0
.
Soit n ∈ N tel que,p our tout ensemble E de cardinal n, Card P(E) = 2
n
.
Considérons un ensemble F de cardinal n +1, et a un élément fixé de F .
L’ensemble E = F \{a} apour cardinal n, il adonc 2
n
parties.
• Les parties de F ne contenantpas a sontexactement les parties de E :i ly
en a2
n
.
• Les parties de F contenant a sont lesr éunions d’une partie de E et du
singleton {a} :i lyen aaussi 2
n
.
Le nombre totaldeparties de F est donc 2×2
n
, c’est-à-dire2
n +1
.
Parrécurrence, tout ensemble de cardinal n possède 2
n
parties.
IMPORTANT
On peut le noteraussi
p
n .
Plus précisément, étudions le nombredeparties de E de cardinal fixé:
Théorème 10
Soit E un ensemble fini de cardinal n. Le nombre de partiesde E de cardinal
p (0 p n)e st l’entier :
n
p
=
n!
p!(n − p)!
Démonstration
Àu ne injection f de [[ 1 , p ]] dans E correspond une image f ([[1, p]] ) , qui
est une partie de E de cardinal p. Réciproquement, toute partie de E de
cardinal p est l’imagede[ [1, p]] par p!i njections distinctes (correspondant aux
permutations de [[ 1 , p ]] ) .
Le nombre de parties de cardinal p est donc
A
p
n
p!
=
n!
p!(n − p)!
.
EXEMPLE
On tire 5c artes dans un jeud e3 2.
Combienya-t-il de résultats possibles ?
Il s’agit de combinaisons de 5éléments
parmi 32 :
il ya
32
5
= 201 376 possibilités.
Une partied ec ardinal p d’une nsemble E est appelée combinaison de p
éléments de E. On utilisel es combinaisons dans tous les problèmes de choix
simultanés de p éléments distincts parmi n, sans considération d’ordre et sans
répétition.
174
Nombresentiers naturels –Combinatoire
EXEMPLE
De combien de façons dix convives
peuvent-ils se placer autour d’une
table? 10! = 3628 800.
Une bijection de E dans E est appelée permutation des éléments de E. On
utilisel es permutations dans tous les problèmes de choix d’un ordre de tous les
éléments d’un ensemble fini.
3.7 • Partiesd’un ensemble fini
Théorème 9
Si E estunensemble fini de cardinal n,
Card P(E) = 2
n
Démonstration
Effectuons une récurrence sur n.
Pour n = 0, E = ∅ et P(E) = {∅} ;C ard P(E) = 1 = 2
0
.
Soit n ∈ N tel que,p our tout ensemble E de cardinal n, Card P(E) = 2
n
.
Considérons un ensemble F de cardinal n +1, et a un élément fixé de F .
L’ensemble E = F \{a} apour cardinal n, il adonc 2
n
parties.
• Les parties de F ne contenantpas a sontexactement les parties de E :i ly
en a2
n
.
• Les parties de F contenant a sont lesr éunions d’une partie de E et du
singleton {a} :i lyen aaussi 2
n
.
Le nombre totaldeparties de F est donc 2×2
n
, c’est-à-dire2
n +1
.
Parrécurrence, tout ensemble de cardinal n possède 2
n
parties.
IMPORTANT
On peut le noteraussi
p
n .
Plus précisément, étudions le nombredeparties de E de cardinal fixé:
Théorème 10
Soit E un ensemble fini de cardinal n. Le nombre de partiesde E de cardinal
p (0 p n)e st l’entier :
n
p
=
n!
p!(n − p)!
Démonstration
Àu ne injection f de [[ 1 , p ]] dans E correspond une image f ([[1, p]] ) , qui
est une partie de E de cardinal p. Réciproquement, toute partie de E de
cardinal p est l’imagede[ [1, p]] par p!i njections distinctes (correspondant aux
permutations de [[ 1 , p ]] ) .
Le nombre de parties de cardinal p est donc
A
p
n
p!
=
n!
p!(n − p)!
.
EXEMPLE
On tire 5c artes dans un jeud e3 2.
Combienya-t-il de résultats possibles ?
Il s’agit de combinaisons de 5éléments
parmi 32 :
il ya
32
5
= 201 376 possibilités.
Une partied ec ardinal p d’une nsemble E est appelée combinaison de p
éléments de E. On utilisel es combinaisons dans tous les problèmes de choix
simultanés de p éléments distincts parmi n, sans considération d’ordre et sans
répétition.
174