Nombres entiers naturels –Combinatoire
EXERCICES
9
3) Déterminer le nombre de triplets (X , Y , Z ) ∈P ( E )
3
tels que X ⊂ Y ⊂ Z .
Coefficients binomiaux
14 1) Démontrerpar récurrence que :
n
k=1
k =
n(n +1)
2
;
n
k= 1
k
2
=
n(n+1)(2n +1)
6
;
n
k= 1
k
3
=
n
2
(n+1)
2
4
.
2) En déduire
n
k=1
k(k +1)(k +2).
3) Retrouver ce résultat en utilisant des coefficients binômiaux.
15 1) Démontrerque, si 1 p n :
p
n
p
= n
n−1
p−1
.
2) En déduire
n
p=1
p
n
p
.
3) Retrouver le résultat en dérivant (1 + x)
n
.
4) Calculer de même
n
p=0
1
p +1
n
p
.
16 Démontrerque, si 0 k p n :
n
k
n−k
p−k
=
p
k
n
p
en utilisant trois façons différentes :
1) àl’aide de l’expression des coefficients binômiaux ;
2) par un raisonnement de dénombrement ;
3) en développant (a + b + c)
n
.
17 Démontrerque, si 0 k min(n, p):
k
i = 0
n
i
p
k−i
=
n+p
k
En déduire
n
i=0
n
i
2 .
18 Calculer (1 + i)
4n
.
En déduire
2n
p=0
(−1)
p
4n
2p
et
2n−1
p=0
(−1)
p
4n
2p+1
.
19 n est un entier de la forme 3k +1 (k∈N).
Montrer que :
n−1
p=0
(−3)
p
2n
2p+1
= 2
2n−1
Indication :Calculer (cos ϕ + i sin ϕ)
2n
, avec ϕ =
π
3
.
Exercice posé aux oraux des concours
20 (Mines 2006)
Soit n ∈ N
∗
.Onveut former des mots avec un alphabet
de n caractères, sans qu’un mot contienned eux fois la
même lettre. Montrer que le nombre total de ces mots est :
M n = [e n!] − 1( où [x]d ésigne la partie entière de x ).
On supposera connu le résultat :
n
p=0
1
p!
< e <
n
p=0
1
p!
+
1
n!
Voir chapitre 14, Application 8.
181