B . Les parties de A contenant a sont de la forme Y = X ∪ {a}, où X est une partie de B ;
puisque a ∈ X , le nombre d’éléments de Y est 1 + |X|.
Notons p B le nombre de parties de B ayant un nombre pair d’éléments et i B le nombre
de parties de B ayant un nombre impair d’éléments. Une partie de A ayant un nombre pair
d’éléments est ou bien une partie de B , ou bien de la forme X ∪ {a}, où X est une partie
de B ayant un nombre impair d’éléments. On en déduit qu’il y a p B + i B parties de A ayant
un nombre pair d’éléments. De même, il y a i B + p B parties de A ayant un nombre impair
d’éléments. Le résultat s’ensuit.
Si A est l’ensemble vide, la seule partie de A est A lui-même : il n’y a pas de parties
de A ayant un nombre impair d’éléments et il y a une seule partie dont le nombre
d’éléments est pair (en fait égal à 0).
Proposition. Soient E un ensemble à p éléments et F un ensemble à n éléments, où
p n 0. Le nombre d’applications f : E → F telles que f (E) = F est
n
p
−
n
1
(n−1)
p +
n
2
(n−2)
p + · · · + (−1)
k
n
k
(n−k)
p + · · · + (−1)
n−1
n
n−1
.
On peut aussi calculer ces nombres de proche en proche : voir l’exercice 8 en fin de chapitre.
Démonstration. Pour tout ensemble A, posons d A =
X⊂A (−1)
|X| , le signe
X⊂A voulant dire que l’on effectue la sommation sur toutes les parties X de l’ensemble A. Si X est
une partie de A, alors (−1)
|X| = 1 si le nombre d’éléments de X est pair et (−1)
|X| = −1
si le nombre d’éléments de X est impair. D’après le résultat préliminaire, on a donc d A = 0
si A est non vide. Si A est l’ensemble vide, alors d A = (−1)
0 = 1. Pour une application
f : E → F , on a donc d F \f (E) = 1 si f (E) = F et d F \f (E) = 0 sinon. Notons S l’ensemble
des applications f : E → F telles que f (E) = F . En notant F
E l’ensemble des applications
de E dans F , nous venons de montrer que le nombre d’éléments de S est
|S| =
f ∈F E
d F \f (E) =
f ∈F E
X⊂F \f (E)
(−1)
|X|
Si f : E → F est une application et si X est une partie de F , on a l’équivalence
X ⊂ F \ f (E) ⇐⇒ f (E) ⊂ F \ X .
La seconde propriété signifie que f est une application de E dans F \ X . Il vient donc
|S| =
X⊂F
f ∈(F \X) E
(−1)
|X| =
X⊂F
(−1)
|X| |F \ X|
p
car il y a |F \ X|
p applications de E dans F \ X . Pour tout entier k tel que 0 k n, posons
s k =
X⊂F
|X|=k
(−1)
k |F \ X|
p = (−1)
k
X⊂F
|X|=k
|F \ X|
p ,
de sorte que l’on a |S| =
0kn s k . Si X est une partie de F à k éléments, F \ X possède
n−k éléments, et comme il y a
n
k
parties de F à k éléments, il vient s k = (−1)
k
n
k
(n−k)
p .
On en déduit S =
0kn (−1)
k
n
k
(n−k)
p qui est la formule annoncée.
66 – ENSEMBLES FINIS
puisque a ∈ X , le nombre d’éléments de Y est 1 + |X|.
Notons p B le nombre de parties de B ayant un nombre pair d’éléments et i B le nombre
de parties de B ayant un nombre impair d’éléments. Une partie de A ayant un nombre pair
d’éléments est ou bien une partie de B , ou bien de la forme X ∪ {a}, où X est une partie
de B ayant un nombre impair d’éléments. On en déduit qu’il y a p B + i B parties de A ayant
un nombre pair d’éléments. De même, il y a i B + p B parties de A ayant un nombre impair
d’éléments. Le résultat s’ensuit.
Si A est l’ensemble vide, la seule partie de A est A lui-même : il n’y a pas de parties
de A ayant un nombre impair d’éléments et il y a une seule partie dont le nombre
d’éléments est pair (en fait égal à 0).
Proposition. Soient E un ensemble à p éléments et F un ensemble à n éléments, où
p n 0. Le nombre d’applications f : E → F telles que f (E) = F est
n
p
−
n
1
(n−1)
p +
n
2
(n−2)
p + · · · + (−1)
k
n
k
(n−k)
p + · · · + (−1)
n−1
n
n−1
.
On peut aussi calculer ces nombres de proche en proche : voir l’exercice 8 en fin de chapitre.
Démonstration. Pour tout ensemble A, posons d A =
X⊂A (−1)
|X| , le signe
X⊂A voulant dire que l’on effectue la sommation sur toutes les parties X de l’ensemble A. Si X est
une partie de A, alors (−1)
|X| = 1 si le nombre d’éléments de X est pair et (−1)
|X| = −1
si le nombre d’éléments de X est impair. D’après le résultat préliminaire, on a donc d A = 0
si A est non vide. Si A est l’ensemble vide, alors d A = (−1)
0 = 1. Pour une application
f : E → F , on a donc d F \f (E) = 1 si f (E) = F et d F \f (E) = 0 sinon. Notons S l’ensemble
des applications f : E → F telles que f (E) = F . En notant F
E l’ensemble des applications
de E dans F , nous venons de montrer que le nombre d’éléments de S est
|S| =
f ∈F E
d F \f (E) =
f ∈F E
X⊂F \f (E)
(−1)
|X|
Si f : E → F est une application et si X est une partie de F , on a l’équivalence
X ⊂ F \ f (E) ⇐⇒ f (E) ⊂ F \ X .
La seconde propriété signifie que f est une application de E dans F \ X . Il vient donc
|S| =
X⊂F
f ∈(F \X) E
(−1)
|X| =
X⊂F
(−1)
|X| |F \ X|
p
car il y a |F \ X|
p applications de E dans F \ X . Pour tout entier k tel que 0 k n, posons
s k =
X⊂F
|X|=k
(−1)
k |F \ X|
p = (−1)
k
X⊂F
|X|=k
|F \ X|
p ,
de sorte que l’on a |S| =
0kn s k . Si X est une partie de F à k éléments, F \ X possède
n−k éléments, et comme il y a
n
k
parties de F à k éléments, il vient s k = (−1)
k
n
k
(n−k)
p .
On en déduit S =
0kn (−1)
k
n
k
(n−k)
p qui est la formule annoncée.
66 – ENSEMBLES FINIS