Chapitre 3
Dénombrement,
permutations, graphes
1. Ensembles finis
1.1 Définition et propriétés
Un ensemble E est fini s’il possède un nombre fini d’éléments.
Si E est un ensemble fini ayant au moins un élément, alors en numérotant ses éléments
à partir de 1, on obtient E = {a 1 ,a 2 ,. . .,a n }. L’entier n est le nombre d’éléments de E .
Il y a en général plusieurs façons de numéroter les éléments de E , mais le nombre
d’éléments ne dépend pas de la numérotation choisie. On convient que l’ensemble vide
est fini et que son nombre d’éléments est zéro.
Notation : Notons |E| le nombre d’éléments de l’ensemble fini E .
Des ensembles finis E et F ont le même nombre d’éléments si et seulement
s’il existe une application bijective de E dans F .
Voici des propriétés très simples concernant les parties d’un ensemble fini.
Proposition. Soit E un ensemble fini à n éléments.
® Toute partie de E est finie et possède au plus n éléments.
® Si A est une partie de E et si A possède n éléments, alors A = E .
Proposition. Si A et B sont des parties finies d’un ensemble, alors la partie A ∪ B est
finie et l’on a
|A ∪ B| + |A ∩ B| = |A| + |B| .
Démonstration. Si l’intersection A ∩ B est vide, le nombre d’éléments de A ∪ B est |A| + |B|
et la formule est vraie. Dans le cas général, les parties A et B \ (A ∩ B) sont disjointes et leur
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 57
Dénombrement,
permutations, graphes
1. Ensembles finis
1.1 Définition et propriétés
Un ensemble E est fini s’il possède un nombre fini d’éléments.
Si E est un ensemble fini ayant au moins un élément, alors en numérotant ses éléments
à partir de 1, on obtient E = {a 1 ,a 2 ,. . .,a n }. L’entier n est le nombre d’éléments de E .
Il y a en général plusieurs façons de numéroter les éléments de E , mais le nombre
d’éléments ne dépend pas de la numérotation choisie. On convient que l’ensemble vide
est fini et que son nombre d’éléments est zéro.
Notation : Notons |E| le nombre d’éléments de l’ensemble fini E .
Des ensembles finis E et F ont le même nombre d’éléments si et seulement
s’il existe une application bijective de E dans F .
Voici des propriétés très simples concernant les parties d’un ensemble fini.
Proposition. Soit E un ensemble fini à n éléments.
® Toute partie de E est finie et possède au plus n éléments.
® Si A est une partie de E et si A possède n éléments, alors A = E .
Proposition. Si A et B sont des parties finies d’un ensemble, alors la partie A ∪ B est
finie et l’on a
|A ∪ B| + |A ∩ B| = |A| + |B| .
Démonstration. Si l’intersection A ∩ B est vide, le nombre d’éléments de A ∪ B est |A| + |B|
et la formule est vraie. Dans le cas général, les parties A et B \ (A ∩ B) sont disjointes et leur
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 57