Proposition. Soient E et F = {b 1 . . . , b n } des ensembles finis et soit f : E → F une
application. Pour chaque entier i ∈ {1, . . . , n}, soit A i l’ensemble des antécédents de b i .
Alors on a |A 1 | + · · · + |A n | = |E|.
Démonstration. On sait (page 21) que les parties A i et A j n’ont pas d’élément en commun
si i = j et que la réunion des parties A i est l’ensemble E tout entier. Le nombre d’éléments
de E est donc la somme |A 1 | + · · · + |A n |.
Voici des propriétés importantes concernant les applications entre des ensembles finis
ayant le même nombre d’éléments.
Proposition. Soient E et F des ensembles finis ayant le même nombre d’éléments et
soit f : E → F une application.
i) L’application f est une bijection si et seulement si
f (E)
= |F |.
ii) L’application f est une bijection si et seulement si tout élément de F a au plus un
antécédent par f .
Démonstration. Si f est une bijection, alors par définition, on a f (E) = F et tout élément
de F a exactement un antécédent par f .
Posons F = {b 1 , . . . , b n } et pour tout entier i compris entre 1 et n, notons A i l’ensemble des
antécédents de b i . D’après la proposition précédente, on a |E| = |A 1 | + · · · + |A n | et comme
|E| = n par hypothèse, il vient
(∗)
|A 1 | − 1
+ · · · +
|A n | − 1
= |A 1 | + · · · + |A n | − n = |E| − n = 0
Supposons que f (E) et F ont le même nombre d’éléments. On a donc f (E) = F , car f (E)
est une partie de F . Puisque tout élément de f (E) possède par définition un antécédent par
f , on en déduit que tout élément de F possède au moins un antécédent, autrement dit nous
avons |A i | 1 pour tout i. Chacun des entiers |A i | − 1 est positif ou nul, leur somme est
nulle d’après (∗), donc on a |A i | − 1 = 0 pour tout i : chaque partie A i possède donc un et
un seul élément. Cela veut dire que chaque élément de F a un et un seul antécédent, donc
l’application f est bijective. Nous avons ainsi démontré la propriété (i).
Supposons maintenant que chaque partie A i possède au plus un élément, donc |A i | 1 pour
tout i. Les entiers |A i | − 1 sont négatifs ou nuls, leur somme est nulle d’après (∗), donc ils
sont tous nuls. Ainsi l’on a |A i | = 1 pour tout i et l’on conclut comme précédemment que f
est une bijection, ce qui démontre (ii).
Principe des tiroirs. Soient E et F des ensembles finis et soit f :E →F une application.
Si |E|>|F |, alors il existe des éléments a et a
appartenant à E tels que a =a
et f (a)=f (a
).
Démonstration. Reprenons les notations introduites dans la démonstration précédente et
supposons |E| > |F |. On a donc |A 1 | + · · · + |A n | = |E| > n. Puisque les nombres |A i | sont
des entiers positifs ou nuls, on en déduit que l’un au moins est strictement supérieur à 1.
Soit i tel que |A i | > 1. Alors il existe dans A i au moins deux éléments a et a
différents et
l’on a f (a) = b i , f (a
) = b i , donc f (a) = f (a
).
Cette propriété s’appelle le principe des tiroirs, car lorsqu’on range plus de n objets
dans n tiroirs, l’un des tiroirs doit contenir au moins deux objets.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 59
application. Pour chaque entier i ∈ {1, . . . , n}, soit A i l’ensemble des antécédents de b i .
Alors on a |A 1 | + · · · + |A n | = |E|.
Démonstration. On sait (page 21) que les parties A i et A j n’ont pas d’élément en commun
si i = j et que la réunion des parties A i est l’ensemble E tout entier. Le nombre d’éléments
de E est donc la somme |A 1 | + · · · + |A n |.
Voici des propriétés importantes concernant les applications entre des ensembles finis
ayant le même nombre d’éléments.
Proposition. Soient E et F des ensembles finis ayant le même nombre d’éléments et
soit f : E → F une application.
i) L’application f est une bijection si et seulement si
f (E)
= |F |.
ii) L’application f est une bijection si et seulement si tout élément de F a au plus un
antécédent par f .
Démonstration. Si f est une bijection, alors par définition, on a f (E) = F et tout élément
de F a exactement un antécédent par f .
Posons F = {b 1 , . . . , b n } et pour tout entier i compris entre 1 et n, notons A i l’ensemble des
antécédents de b i . D’après la proposition précédente, on a |E| = |A 1 | + · · · + |A n | et comme
|E| = n par hypothèse, il vient
(∗)
|A 1 | − 1
+ · · · +
|A n | − 1
= |A 1 | + · · · + |A n | − n = |E| − n = 0
Supposons que f (E) et F ont le même nombre d’éléments. On a donc f (E) = F , car f (E)
est une partie de F . Puisque tout élément de f (E) possède par définition un antécédent par
f , on en déduit que tout élément de F possède au moins un antécédent, autrement dit nous
avons |A i | 1 pour tout i. Chacun des entiers |A i | − 1 est positif ou nul, leur somme est
nulle d’après (∗), donc on a |A i | − 1 = 0 pour tout i : chaque partie A i possède donc un et
un seul élément. Cela veut dire que chaque élément de F a un et un seul antécédent, donc
l’application f est bijective. Nous avons ainsi démontré la propriété (i).
Supposons maintenant que chaque partie A i possède au plus un élément, donc |A i | 1 pour
tout i. Les entiers |A i | − 1 sont négatifs ou nuls, leur somme est nulle d’après (∗), donc ils
sont tous nuls. Ainsi l’on a |A i | = 1 pour tout i et l’on conclut comme précédemment que f
est une bijection, ce qui démontre (ii).
Principe des tiroirs. Soient E et F des ensembles finis et soit f :E →F une application.
Si |E|>|F |, alors il existe des éléments a et a
appartenant à E tels que a =a
et f (a)=f (a
).
Démonstration. Reprenons les notations introduites dans la démonstration précédente et
supposons |E| > |F |. On a donc |A 1 | + · · · + |A n | = |E| > n. Puisque les nombres |A i | sont
des entiers positifs ou nuls, on en déduit que l’un au moins est strictement supérieur à 1.
Soit i tel que |A i | > 1. Alors il existe dans A i au moins deux éléments a et a
différents et
l’on a f (a) = b i , f (a
) = b i , donc f (a) = f (a
).
Cette propriété s’appelle le principe des tiroirs, car lorsqu’on range plus de n objets
dans n tiroirs, l’un des tiroirs doit contenir au moins deux objets.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 59