(v) Si E = F est fini on sait qu’une fonction de E dans F est bijective si et seulement
si elle est injective donc d’après le résultat précédent il y a n(n−1)(n−2) . . . (n−n+1) = n!
bijections.
Introduisons maintenant une notation très utile en combinatoire :
Définition: Soit F un ensemble de cardinal n et soit 0 ≤ p ≤ n, le nombre de parties
n
p
de F ayant p éléments se note Cn ou p .
THÉORÈME: On a les formules suivantes :
n(n−1)(n−2)...(n−p+1) n!
(i) Cnp = p! = p!(n−p)!
(ii) Cnp = Cnn−p
p p−1
(iii) Cnp = Cn−1 + Cn−1
Démonstration: (i) Un sous-ensemble à p éléments de F est donné à permutation
près de ses éléments (il y a p! permutations d’après le théorème précédent) par une in-
jection de {0, 1, 2, . . . , p} dans F ; il y a n(n − 1)(n − 2) . . . (n − p + 1) injections et donc
n(n−1)(n−2)...(n−p+1)
p! parties à p éléments.
Démontrons maintenant les deux propriétés (ii) et (iii). On peut bien sûr démontrer
n!
ces formules en utilisant la formule Cnp = p!(n−p)! (vérifiez-le à titre d’exercice) mais nous
trouvons plus instructive une démonstration en termes d’ensembles à partir de la définition
des Cnp .
(ii) Soit E un ensemble de cardinal n. L’application A 7→ CE A définit une bijection
entre l’ensemble des parties de E à p éléments et l’ensemble des parties de E à n − p
éléments, d’où la formule (ii).
(iii) Soit E un ensemble de cardinal n et soit x ∈ E. L’ensemble des parties de E à p
éléments se répartit en deux sous-ensembles disjoints : l’ensemble des parties à p éléments
de E contenant l’élément x et l’ensemble des parties à p éléments de E ne contenant pas
l’élément x. Le premier est en bijection avec l’ensemble des parties à p − 1 éléments de
p−1
E \ {x} qui a pour cardinal Cn−1 , et le second est en bijection avec l’ensemble des parties
p
à p éléments de E \ {x} qui a pour cardinal Cn−1 , d’où le résultat cherché.
Remarque : Si l’on écrit dans un tableau les coefficients Cnp (où n sera le numéro de la
ligne et p le numéro de la colonne), les propriétés (i) et (ii) se traduisent par la symétrie de
chaque ligne et en observant que chaque coefficient est la somme de deux coefficients de la
ligne précédente : celui situé juste au-dessus et son prédécesseur. Ces remarques permet-
tent d’ailleurs de calculer très facilement les premiers coefficients. Ce tableau s’appelle le
triangle de Pascal (bien qu’il ait été connu par exemple des mathématiciens arabes avant
sa redécouverte par Pascal).
19
