Nombresentiersnaturels –Combinatoire
COURS
9
Démonstration
Soit E = {e 1 , e 2 , ··· ,e p }.
L’application
F
E
→ F
p
f
→ (f (e 1 ), ··· ,f (e p ))
estbijective.
Donc F
E
est fini et Card (F
E
) = Card (F
p
) = (Card F )
p
= (Card F )
Card E
.
3.6 • Injections
IMPORTANT
On rappelle que n!( lire factorielle
n)d ésigne le produit des n premiers
entiers naturels non nuls.
Par convention 0! = 1.
Théorème 8
Soit E et F deux ensembles finis de cardinaux respectifs :
Card E = p et Card F = n,
avec0 p n
Le nombre d’injections de E dans F est l’entier :
A
p
n = n(n − 1) ···(n−p+1)=
n!
(n−p)!
Démonstration
Raisonnonspar récurrence sur p :
• pour p = 0, il existe une injection de ∅ dans F : A
0
n = 1 =
n!
(n − 0)!
;
• soit p ∈ [[ 1 , n − 1]]t el que le nombre d’injections d’un ensemble de cardinal
p dans F soit A
p
n . Soit E un ensemble de cardinal p +1, et a ∈ E.
Une injection f de E dans F est caractérisée par :
–larestriction injective de f à E\{a} : A
p
n possibilités;
–lechoix de l’élément f (a)q ui ne doit pas appartenir à f (E): n − ppossibilités.
Le nombre d’injections de E dans F est donc :
A
p
n (n − p) =
n!
(n − p)!
(n − p) =
n!
(n − p − 1)!
= A
p+1
n
Par récurrence,lenombre d’injections de E dans F est donc bien A
p
n pour tout
p ∈ [[ 1 , n ]] .
EXEMPLE
Combien ya-t-il de tiercés dans l’ordre
pour dix chevaux au départ ?
Il s’agit d’arrangements de trois chevaux parmidix :1 0 × 9 × 8=720
tiercés dans l’ordre.
Une injection de [[ 1 , p ]] dans F est appelée arrangement de p éléments de F .
C’est une p-liste d’éléments de F distincts deux àdeux. On utilise les arrangements
dans tous les problèmes de choix successifs de p éléments parmi n, sans répétition.
Corollaire8.1
Si E est un ensemble fini de cardinal n, le nombre de bijections de E dans
E est n!.
Démonstration
Comme E est fini, il est équivalent de dire qu’une application de E dans E est
injective ou bijective ;lenombre de bijections de E dans E est donc A
n
n = n!.
 Hachette Livre–HPrépa /Math –Laphotocopie non autorisée est un délit
173