1.

Pour k ≥ 1, on peut écrire

n−1
         
n n n n
(k + 1) =k + =n +
k k k k−1 k

d’où , en notant S la somme cherchée : 1

n  n  
n−1
 X
X n −3
S=n + = n2n−1 + 2n = (n + 2)2n−1
k−1 k
k=1 k=0

Autre solution. Considérons la fonction f définie par f (x) = x(1 + x)n . Alors
S = f 0 (1) or f 0 (x) = (1 + x)n + nx(1 + x)n−1 d’où S = 2n + n2n−1 .
2. Factorisons la différence.

1 + x + x2 (m + 2)x + 1 − (m + 2)x2 − x − 1 − x − x2
(m + 2)x + 1 − = Fig. 1 – Graphe de h
1−x 1−x
mx − (m + 3)x2 ((m + 3)x − m) x
= =
1−x x−1 – Si m > 0
L’inéquation proposée est équivalente (pour m 6= −3) à 0 < h(m) < 1 ⇒ Sm = ] − ∞, 0[ ∪ ]
m
, 1[
m+3
m+3 m 3
x(x − h(m)) < 0 avec h(m) = =1− 3. Les k! et (k + 1)! se simplifient respectivement dans les deux quotients en
x−1 m+3 m+3
permettant une mise en facteur
Le signe de cette expression est facile à évaluer pour x plus grand que
n n


0, 1, h(m) et elle change de signe en chacune de ces valeurs. On doit donc n(n − 1) · · · (n − k + 1) n(n − 1) · · · (n − k)


k+1
classer 0, 1, h(m) suivant m en étudiant le graphe de h qui est une hyperbole.
k
− = −
2n 2n (2n)(2n − 1) · · · (2n − k + 1) (2n)(2n − 1) · · · (2n − k)



(fig 1). On obtient : k k+1

– Si m < −3, n(n − 1) · · · (n − k + 1) n−k

= (1 − )
(2n)(2n − 1) · · · (2n − k + 1) 2n − k
m
0 < 1 < h(m) ⇒ Sm = ]0, 1[ ∪ ] , +∞[ n(n − 1) · · · (n − k + 1) n 1 n(n − 1)(n − 2) · · · (n − k + 1)
m+3 = =
(2n)(2n − 1) · · · (2n − k + 1) 2n − k 2 (2n − 1)(2n − 2) · · · (2n − k)
– Si m = −3, l’inéquation devient
Ce quotient contient k facteurs en haut (compteur entre 0 et k − 1) et en bas
3x (compteur entre 1 et k). On retrouve un quotient de coefficients du binôme
<0 ⇒ Sm = ]0, 1[
x−1 en introduisant des k! en haut et en bas. On en déduit la formule valable
pour k entre 0 et n − 1
– Si −3 < m ≤ 0
n n n




m 1 k
h(m) < 0 < 1 ⇒ Sm = ] − ∞, [ ∪ ]0, 1[ 2n −
k k+1
2n

=
2 2n−1



m+3 k k+1 k

1
 Dans le calcul de la somme S, il faut traiter à part le dernier terme. On démontre de la même manière que

! ΦAB ◦ ΦBA = IdF (B,P(A))
!
n n n



1 1
2n − 2n
S=2 0

n

+ 2n−1
= 2 1 − 2n
+ 2n−1

n

k n n n n On tire la surjectivité de ΦAB de la première équation et l’injectivité de la

deuxième. Les applications ΦAB et ΦBA sont donc des bijections réciproques
Or l’une de l’autre.
2n − 1 2n − 1 2n − 1 2n − 1
         
2n
+ = avec = Supposons A et B finis avec respectivement α et β éléments. D’après le cours
n−1 n n n−1 n sur le dénombrement des applications et celui des parties d’un ensemble, on
donc peut écrire
2n − 1
   
2n
=2 et S = 2 Card(F(A, P(B))) = Card(F(A, P(B))) = (2β )α = 2αβ
n n
3. On suppose maintenant que A = {1, · · · , n} et B = E. Si f est une applica-
Nombre de recouvrements tion de A dans P(E), on pose
1. Exemple. Choisissons A = {1, 2, 3}, B = {x, y, z, t}
E1 = f (1), E2 = f (2), · · · , En = f (n), ϕ = ΦAB (f )
→ {x, y}
 
1 a. Désignons par Ωi l’ensemble des parties de A contenant i alors
f = 2 → {x} 
3 → ∅ x ∈ ϕ−1 (Ωi ) ⇔ ϕ(x) ∈ Ωi
⇔ i ∈ ϕ(x)
alors
→ {1, 2} ⇔ x ∈ f (i)
 
x
y → {1} 
ϕ= Donc ϕ−1 (Ωi ) = f (i).
→ ∅ 

z
t → ∅ b. Utilisons encore la relation fondamentale

2. On peut reformuler les définitions de ΦAB et de ΦBA ∀a ∈ A, ∀b ∈ B : a ∈ ϕ(b) ⇔ b ∈ f (a)

On peut écrire
∀f ∈ F(A, P(B)), ∀a ∈ A, ∀b ∈ B : a ∈ (ΦAB (f ))(b) ⇔ b ∈ f (a)
∀g ∈ F(B, P(A)), ∀a ∈ A, ∀b ∈ B : b ∈ (ΦBA (g))(b) ⇔ a ∈ g(b) ∅ ∈ ϕ(E) ⇔ ∃b ∈ B tq ϕ(b) = ∅
⇔ ∃b ∈ B tq ∀a ∈ A : a 6∈ ϕ(b)
Par conséquent, ∀f ∈ F(A, P(B)), ∀a ∈ A, ∀b ∈ B on a
⇔ ∃b ∈ B tq ∀a ∈ A : b 6∈ f (a)
b ∈ (ΦBA ◦ ΦAB (f ))(a) ⇔ b ∈ (ΦBA (ΦAB (f )))(a) ⇔ ∃b ∈ B tq b 6∈ Ω1 ∪ · · · ∪ Ωn
⇔ a ∈ ΦAB (f ))(b)
L’équivalence des négations des deux propositions fournit la relation
⇔ b ∈ f (a) demandée.
On en déduit que le nombre de n-recouvrements est aussi le nombre
Ceci étant valable pour tous les f ∈ F(A, P(B)) on a bien d’applications de E vers P(E) − ∅ soit (si p est le nombre d’éléments de
E) :
ΦBA ◦ ΦAB = IdF (A,P(B))
(2p − 1)n