f est injective.
On conclut que (ii) équivaut à (iii) ; par ailleurs (i) équivaut par définition
à (ii) et (iii) d’où le théorème.
Remarque : On voit en particulier que si x ∈ E et E est fini alors E \ {x} n’est pas
en bijection avec E. Ceci est une caractérisation des ensembles finis.
Une autre application simple des ensembles finis est le principe des tiroirs ; “si on range
n + 1 chaussettes dans n tiroirs, l’un (au moins) des tiroirs contiendra deux chaussettes”
(on laisse la preuve en exercice).
Il est naturel, sachant qu’une ensemble est fini de chercher à déterminer son cardi-
nal (un entier naturel). On appelle combinatoire cette partie des mathématiques. Voici
quelques résultats utiles.
THÉORÈME: Soient E et F des ensembles finis de cardinaux m et n respectivement,
alors :
(i) card(E) + card(F ) = card(E ∩ F ) + card(E ∪ F )
(ii) card(E × F ) = mn
(iii) Soit F(E, F ) l’ensemble des applications de E vers F alors card(F(E, F )) = nm .
En particulier card(P(E)) = 2m .
(iv) Le nombre d’injection de E dans F est 0 si m > n et n(n−1)(n−2) . . . (n−m+1)
si m ≤ n.
(v) L’ensemble des bijections de F vers F a pour cardinal n! = n(n − 1)(n − 2) . . . 2.1
Démonstration: (i) Commençons par observer que dans le cas plus facile où E ∩F = ∅,
la formule est évidente ; en effet si X = A ∪ B avec A ∩ B = ∅ alors card(X) = card(A) +
card(B). Revenons au cas général et posons E 0 := E \ (E ∩ F ), alors E ∪ F est union
disjointe de F et E 0 donc card(E ∪ F ) = card(F ) + card(E 0 ). Mais E est union disjointe
de E 0 et E ∩ F donc on a aussi : card(E) = card(E 0 ) + card(E ∩ F ) et on tire de ces deux
égalités la formule : card(E) + card(F ) = card(E ∩ F ) + card(E ∪ F )
(ii) On peutPécrire E × F = ∪x∈E {x} × F ; or ces ensembles sont disjoints donc on a
card(E × F ) = x∈E card({x} × F ). Mais F est en bijection avec chacun des P ensembles
{x} × F par l’application y 7→ (x, y) donc card({x} × F ) = n et card(E × F ) = x∈E n =
mn.
(iii) Pour construire une fonction de E = {a1 , a2 , . . . , am } vers F il faut choisir f (a1 )
(il y a n choix possibles), f (a2 ) (il y a n choix possibles),. . . etc. Il y a donc n×n . . . n = nm
fonctions de E vers F .
Soit A un sous-ensemble de E, on lui associe la fonction fA : E → {0, 1} définie par
fA (x) = 1 si x ∈ A et fA (x) = 0 si x ∈ / A (la fonction fA s’appelle la fonction caractéristique
de A). On obtient ainsi une bijection entre P(E) et F(E, {0, 1}) (la bijection réciproque est
donnée par f 7→ {x ∈ E | f (x) = 1}). On conclut que card(P(E)) = card({0, 1})m = 2m .
(iv) Tout d’abord, il est clair que si card(E) > card(F ) il n’existe aucune injection de
E dans F . Si maintenant E = {a1 , a2 , . . . , am } et m ≤ n, pour construire une application
injective de E dans F on doit choisir f (a1 ) ∈ F (il y a n choix possibles) puis f (a2 ) ∈
F \ {f (a1 )} (il y a n − 1 choix possibles) puis f (a3 ) ∈ F \ {f (a1 ), f (a2 )} (il y a n − 2 choix
possibles) et ainsi de suite. On obtient donc bien en tout n(n − 1)(n − 2) . . . (n − m + 1)
injections.
18
