Nombresentiersnaturels –Combinatoire
COURS
9
On aalors :
(a + b)
n+1
= (a + b)(a + b)
n
= a
n
p=0
n
p
a
n−p
b
p
+ b
n
p=0
n
p
a
n−p
b
p
=
n
p=0
n
p
a
n−p+1
b
p
+
n
p=0
n
p
a
n−p
b
p+1
= a
n+1
+
n
p=1
n
p
a
n−p+1
b
p
+
n−1
p=0
n
p
a
n−p
b
p+1
+ b
n+1
= a
n+1
+
n
p=1
n
p
a
n−p+1
b
p
+
n
q=1
n
q−1
a
n−q+1
b
q
+ b
n+1
(en posant q = p +1dans le 3
e
terme)
= a
n+1
+
n
p=1
(
n
p
+
n
p−1
) a
n−p+1
b
p
+ b
n+1
= a
n+1
+
n
p=1
n+1
p
a
n−p+1
b
p
+ b
n+1
=
n+1
p=0
n+1
p
a
n+1−p
b
p
.
APPLICATION 6
Troismodes de démonstration pour les formules de combinatoire
Lesf ormules mettant en jeu des coefficients binomiaux
peuventêtre démontrées d’au moins trois façons :
–par récurrence ;
–par un raisonnement de dénombrement ;
–enutilisant la formule du binôme.
Exemple :Démontrer quepour tout (n, p) ∈ N
2
tel que
p n :
n
k=p
k
p
=
n+1
p+1
1) Par récurrence sur n :
• Pour n = 0( ce qui implique p = 0), on ab ien
0
0
=
1
1
.
• Soit n un entier vérifiantl ar elation quel que soit
p n.
–Pour tout p n :
n+1
k=p
k
p
=
n
k=p
k
p
+
n+1
p
=
n+1
p+1
+
n+1
p
=
n+2
p+1
–Pour p = n +1, on aaussi :
n+1
k=p
k
p
=
n+1
n+1
= 1 =
n+2
p+1
La relation estv érifiée pour n +1 , quel que soit
p n +1.
Par récurrence, elle est donc vérifiée pour tout n ∈ N
et tout p n.
2) Dénombrement
Dénombrons les parties à p +1 éléments de l’intervalle [[ 0 , n ]] . Si k estl ep lus grand élément d’une
telle partie (k varied e p à n ) , il reste àc hoisir p
éléments dans l’intervalle [[ 0 , k − 1]]. Le nombre total
de ces parties est donc :
n+1
p+1
=
n
k=p
k
p
3) Àl’aide de la formule du binôme
La factorisation du polynôme X
n+1
− 1n ous donne :
∀x ∈ R
(1 + x)
n+1
− 1 = x
n
k=0
(1 + x)
k
En identifiantles coefficients des termes en x
p+1
, on
obtient:
n +1
p+1
=
n
k=p
k
p
Pour s’entraîner:ex. 14 à19
Hachette Livre –HPrépa /Math –Laphotocopie non autorisée est un délit
177