a) Montrer que N est le nombre d’éléments de l’ensemble A
∩ B
, où A
= S \ A et
B
= S \ B.
b) Montrer que |A
∩ B
| = |S| − |A| − |B| + |A ∩ B|.
c) Montrer que |A| est le nombre de solutions (u,y,z) de l’équation u + y + z = n − a,
où u, y, z sont des entiers strictement positifs (s’inspirer de l’exemple page 64).
En déduire |A| =
n−a−1
2
.
d) Montrer de même que l’on a |B| =
n−b−1
2
et |A ∩ B| =
n−a−b−1
2
. En déduire la
valeur de N .
6. Un vacancier veut envoyer des cartes postales à quatre personnes. Il achète sept
cartes différentes. De combien de façons peut-il toutes les expédier ?
7
@ . Pour tout entier n 1, posons E n = {1, 2, . . . , n}.
a) Soit f : E n+1 → E n une application. Montrer que si f (E n+1 ) = E n , il existe un
unique élément b ∈ E n ayant deux antécédents.
b) En déduire qu’il y a n!
n(n+1)
2
applications de E n+1 dans E n ayant pour image E n .
8. Autre calcul du nombre d'applications ayant pour image leur ensemble d'arrivée (page 66).
Soient p et n des entiers positifs tels que p n. Si U est un ensemble à p éléments
et si V est un ensemble à n éléments, on note s(p, n) le nombre d’applications
h : U → V telles que h(U ) = V . On pose E p = {1, 2, . . . , p} et E n = {1, 2, . . . , n}.
a) Soit B une partie de E n . Montrer que si B possède k éléments, il y a s(p, k)
applications f : E p → E n telles que f (E p ) = B.
b) En déduire l’égalité n
p =
n
k=1
n
k
s(p, k).
c) Expliquer comment cette égalité permet de calculer les nombres s(p, k) de proche
en proche.
9. Nombre de partitions d'un ensemble. Soit E un ensemble à p éléments et soit n un entier tel que 1 n p. Une n-partition de E est la donnée de n parties A 1 ,A 2 ,. . .,A n
de E formant une partition de E : cela signifie que les parties A i sont non vides,
deux à deux disjointes et que leur réunion est E .
a) Expliquer comment une application f :E →{1,2,. . .,n} telle que f (E)={1,2,. . .,n}
détermine une n-partition de E : considérer les parties A i = {x ∈ E | f (x) = i}.
b) Montrer qu’il y a autant de n-partitions de E que d’applications f :E →{1,2,. . .,n}
telles que f (E) = {1, 2, . . . , n}.
10
@ . Étude d'une permutation
a) Décomposer en cycles à supports disjoints la permutation s suivante :
i 1 2 3 4 5 6 7 8 9 10 11 12
s(i) 9 12 8 1 4 3 2 10 5 11 6 7
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 97
∩ B
, où A
= S \ A et
B
= S \ B.
b) Montrer que |A
∩ B
| = |S| − |A| − |B| + |A ∩ B|.
c) Montrer que |A| est le nombre de solutions (u,y,z) de l’équation u + y + z = n − a,
où u, y, z sont des entiers strictement positifs (s’inspirer de l’exemple page 64).
En déduire |A| =
n−a−1
2
.
d) Montrer de même que l’on a |B| =
n−b−1
2
et |A ∩ B| =
n−a−b−1
2
. En déduire la
valeur de N .
6. Un vacancier veut envoyer des cartes postales à quatre personnes. Il achète sept
cartes différentes. De combien de façons peut-il toutes les expédier ?
7
@ . Pour tout entier n 1, posons E n = {1, 2, . . . , n}.
a) Soit f : E n+1 → E n une application. Montrer que si f (E n+1 ) = E n , il existe un
unique élément b ∈ E n ayant deux antécédents.
b) En déduire qu’il y a n!
n(n+1)
2
applications de E n+1 dans E n ayant pour image E n .
8. Autre calcul du nombre d'applications ayant pour image leur ensemble d'arrivée (page 66).
Soient p et n des entiers positifs tels que p n. Si U est un ensemble à p éléments
et si V est un ensemble à n éléments, on note s(p, n) le nombre d’applications
h : U → V telles que h(U ) = V . On pose E p = {1, 2, . . . , p} et E n = {1, 2, . . . , n}.
a) Soit B une partie de E n . Montrer que si B possède k éléments, il y a s(p, k)
applications f : E p → E n telles que f (E p ) = B.
b) En déduire l’égalité n
p =
n
k=1
n
k
s(p, k).
c) Expliquer comment cette égalité permet de calculer les nombres s(p, k) de proche
en proche.
9. Nombre de partitions d'un ensemble. Soit E un ensemble à p éléments et soit n un entier tel que 1 n p. Une n-partition de E est la donnée de n parties A 1 ,A 2 ,. . .,A n
de E formant une partition de E : cela signifie que les parties A i sont non vides,
deux à deux disjointes et que leur réunion est E .
a) Expliquer comment une application f :E →{1,2,. . .,n} telle que f (E)={1,2,. . .,n}
détermine une n-partition de E : considérer les parties A i = {x ∈ E | f (x) = i}.
b) Montrer qu’il y a autant de n-partitions de E que d’applications f :E →{1,2,. . .,n}
telles que f (E) = {1, 2, . . . , n}.
10
@ . Étude d'une permutation
a) Décomposer en cycles à supports disjoints la permutation s suivante :
i 1 2 3 4 5 6 7 8 9 10 11 12
s(i) 9 12 8 1 4 3 2 10 5 11 6 7
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 97