Dénombrement, binôme de Newton

1. Enoncé des exercices

1.1. Les basiques

1. Soit n ∈ N et Pn (x) = (x + 1)n − (x − 1)n . Quel est le degré de Pn , quel est son coefficient dominant ?
2. Calculer simplement 999 9993
Xn
3. Calculer Cnk 3k−1 en fonction de n.
k=1
5 5
4. Soit g(x) = (cos x + sin x) + (cos x − sin x) , montrer que g(x) s’exprime uniquement en fonction de cos(x).
X p−k
5. Calculer pour p ≤ n, Cnk Cn−k
0≤k≤p
n
X
6. Calculer kCnk .
k=0
n
X
7. On considère, pour n ≥ 0, la fonction f(x) = (1 + ex )n . En dérivant deux fois f , donner l’expression de k2 Cnk
k=0

1.2. Les techniques

n
X
1. Calculer pour n ∈ N, (a, b) ∈ R2 , Cnk cos (ak + b).
k=0
n
X cos(kx)
2. Calculer pour n entier (−1)n−k Cnk
cosk (x)
k=0
n
X n
X
3. Soient p et q deux réels tels que p + q = 1, calculer kCnk pk q n−k puis k(k − 1)Cnk pk q n−k
k=0 k=0
4. Soit E un ensemble à n éléments, déterminer le nombre de couples (A, B) de parties telles que A ⊂ B.

1.3. Les exotiques

1. Baltic-Way 1998 (Olympiades des pays Baltes)

n
X µ ¶
2 k−1 1+x
Soit Pk (x) = 1 + x + x + ... + x . Montrer que Cnk Pk n−1
(x) = 2 Pn
2
k=1
2
2. Soit E de cardinal n. Déterminer le nombre de couples (A, B) ∈ P (E) tels que A 6⊂ B et B 6⊂ A
3. Combien y a-t-il de surjections de {1, 2, ..., n + 1} dans {1, 2, ..., n} ?

1.4. Les olympiques

1. Soit E un ensemble à n éléments, déterminer le nombre de couples (A, B) de parties distinctes telles que A ∩ B = ∅.
X X X
2. Calculer Card (A) , Card (A ∩ B) , Card (A ∪ B) où E est Þni de cardinal n.
A⊂E A⊂E A⊂E
B⊂E B⊂E


 
Géry Huvent. Lycée Baggio. PTSI1 2

2. Solution des exercices

2.1. Les basiques

n n ¡ ¢
1. On développe avec le binôme, (x + 1) − (x − 1) = xn + nxn−1 + ... + 1 − xn − nxn−1 − ... = 2nxn−1 + ...
Si n = 0, P0 (x) = 0, sinon deg Pn = n − 1 et le coefficient dominant est 2n.
¡ ¢3
2. On a 999 9993 = 106 − 1 = 1018 − 3 × 1012 + 3 × 106 − 1
¡ ¢
= 1012 × 106 − 3 + 3 × 106 − 1 = 1012 × (999 997) + 2 999 999 = 999 997 000 002 999 999
Xn n
1 X k k n−k 1 4n − 1
3. Il s’agit pratiquement d’un binôme, on a Cnk 3k−1 = Cn 3 1 − =
3 3 3
k=1 k=0

4. Un calcul élémentaire donne g (x) = 2 cos x + 20 cos x sin x + 10 cos x sin4 x

5 3 2
¡ ¢ ¡ ¢2
= 2 cos5 x + 20 cos3 x 1 − cos2 x + 10 cos x 1 − cos2 x = −8 cos5 x + 10 cos x
p−k n! (n − k)! p! n!
5. On a Cnk Cn−k = × = × = Cpk Cnp .
X k! (n − k)!
X (p − k)! × (n
X − p)! k! (p − k)! p! (n − p)!
p−k
D’où Cnk Cn−k = Cpk Cnp = Cnp Cpk = 2p Cnp .
0≤k≤p 0≤k≤p 0≤k≤p
6. On dispose de deux méthodes.
n k−1 Pn Pn Pn P
Ou bien, on utilise le cours Cnk = Cn−1 k−1
si k ≥ 1 ainsi k=0 kCnk = k=1 kCnk = k=1 nCn−1 = n nk=1 Cn−1
k−1
.
k Pn ¡ ¢ P
k−1 n−1 n
Remarquez que l’on a exclus l’indice k = 0. EnÞn k=1 Cn−1 = C00 + C11 + ... + Cn−1 = 2n−1 . D’où k=0 kCnk =
n2n−1 .
n Pn n−1 P
Ou bien on utilise le binôme. On a (1 + x) = k=0 Cnk xk ce qui donne, en dérivant, n (1 + x) = nk=0 kCnk xk . Il
ne reste plus qu’a faire x = 1 pour obtenir le résultat.
Xn Xn
7. f (x) = (1 + ex )n , f peut aussi s’écrire f(x) = Cnk (ex )k = Cnk ekx .
k=0 k=0
En dérivant les deux expressions, puis en faisant k = 0, on obtient une relation.
f 0 (x) = nex (1 + ex )n−1 = n (1 + ex − 1) (1 + ex )n−1 = n(1 + ex )n − n(1 + ex )n−1 (expression valable si n = 0 )
f 00 (x) = n2 ex (1 + ex )n−1 − n(n − 1)ex (1 + ex )n−2 (expression encore valable si n = 1 )
Xn
0
¡ ¢0
Avec l’autre expression, on obtient f (x) = kCnk ekx , car ekx = kekx , ceci même si k = 0.
k=0
µ ¶ n
X
00 n kx 2
Puis f (x) = k e .
k
k=0
n
X µ ¶
2 n
On a alors pour x = 0, k = n2 (1 + 1)n−1 − n(n − 1)(1 + 1)n−2 = n (n + 1) 2n−2
k
k=0

2.2. Les techniques

n
à n ! à n
! Ã n
!
X X X X
1. Cnk cos (ak + b) = Re Cnk ei(ak+b)
= Re e ib
Cnk eiak
= Re e ib
Cnk eiak 1n−k
k=0
¡ ¡ ¢n ¢ ³
k=0
¡ ¢ ´ k=0
¡ ¢ ¡ ¢
k=0
= Re 2 cosn a2 ei(b+n 2 ) = 2n cosn a2 cos na
a
= Re eib 1 + eia n
2 + b
n
à n µ ¶ k
! µ ¶n
X n−k k cos(kx)
X n−k k eix eix
2. (−1) Cn = Re (−1) Cn = Re −1
cosk (x) cos(x) cos(x)
k=0 ¡ k=0 ¢
= Re (i tan(x))n = Re ei 2 tann (x)
nπ

Xn ½
cos(kx) ¡ nπ ¢ 0 si n est impair
Ainsi (−1)n−k Cnk = cos tann
(x) =
cosk (x) 2 (−1)p tan2p (x) si n = 2p
k=0


 
Géry Huvent. Lycée Baggio. PTSI1 3

P
n
3. La première idée que l’on peut avoir est que 1 = 1n = (p + q)n = Cnk pk q n−k . Il reste à faire apparaître ce kCnk
k=0
(pour k (k − 1) Cnk , il s’agit sans doute de la même technique). Le seul moyen de faire ”tomber” le k qui est en exposant
Pn
est de dériver. Si on considère la fonction f (x) = Cnk xk q n−k = (x + q)n , f est un polynôme donc est dérivable
k=0
P
n
n−1 P
n
0
sur R. f (x) = kCnk xk−1 q n−k = n (x + q) et xf 0 (x) = kCnk xk q n−k = xn (x + q)n−1 . On en déduit que
k=0 k=0
P
n
n−1
kCnk pk q n−k 0
= pf (p) = np (p + q) = np.
k=0
P
n P
n
De la même façon x2 f 00 (x) = k (k − 1) Cnk xk q n−k = x2 n (n − 1) (x + q)n−2 et k(k − 1)Cnk pk q n−k = n (n − 1) p2 .
k=0 k=0
n! (n−1)! k−1
Remarque : On peut aussi utiliser kCnk = k k!(n−k)! = n (k−1)!(n−1−(k−1))! = nCn−1 pour
n ≥ 1, k ≥ 1. Cette relation
n
X n
X
k−1 k n−k
étant encore valable si n = 0 ou si k = 0. On a alors kCnk pk q n−k = nCn−1 p q
k=0 k=1
n−1
X n−1
X
j j n−1
= n Cn−1 pj+1 q n−1−j = np Cn−1 pj q n−1−j = np (p + q) = np. L’autre somme peut aussi se calculer de
j=k−1
j=0 j=0
cette manière.
4. Si vous êtes en panne d’idée, une bonne méthode consiste à construire tous les couples pour E = {1, 2, 3} . Pour cela
on commence par choisir une partie B, par exemple B = {1, 3} , puis on choisit A incluse dans B. C’est cette idée qu’il
faut développer.
Pour construire un couple convenable, on choisit B et pour B Þxée, on choisit A dans P (B) quelconque. Si B a k
éléments dans P (E) , on dispose de Cnk choix pour B, et de 2k choix pour A. Il y a donc Cnk 2k couples (A, B) tels que
Pn
A ⊂ B et Card (B) = k. On a donc au total Cnk 2k = 3n couples possibles.
k=0

2.3. Les exotiques

xk −1 Pn k 1
¡Pn k k
Pn k
¢
1. On a si x 6= 1, Pk (x) = x−1 ,ainsi k=1 Cn Pk (x) = x−1 k=1 Cn x − k=1 Cn
1 n (x+1)n −2n ¡ ¢ ( 1+x n
2 ) −1
= n
x−1 ([(x + 1) − 1] − [2 − 1]) = x−1 , et 2n−1 Pn 1+x
2 = 2n−1 1+x −1
2
(x+1)n −2n
= x−1 . L’égalité est donc vraie
pour x 6= 1, mais comme les deux membres sont des polynômes, elle est vraie
partout (par continuité ou prolongement des identités algébriques).
n o
2 2
2. Notons A = (A, B) ∈ P (E) , A ⊂ B ou B ⊂ A ,alors A = P (E) \ A est l’ensemble des couples cherchés.
n o n o
2 2
Posons A1 = (A, B) ∈ P (E) , A ⊂ B et A2 = (A, B) ∈ P (E) , B ⊂ A . On a Card (A1 ) = Card (A2 ) et
n o
A1 ∩ A2 = (A, B) ∈ P (E)2 , A = B a pour cardinal 2n .
Calculons le cardinal de A2 . Soit A ⊂ P (E) de cardinal k, il y a 2k parties B incluses dans A. Ainsi Card (A2 ) =
Pn k k n
¡ ¢ n n n
k=0 Cn 2 = 3 . EnÞn, Card A = 4 − (2 × 3 − 2 )
3. Une application de {1, 2, ..., n + 1} dans {1, 2, ..., n} est surjective si un des éléments a deux antécédents et les autres un
2
seul. On a Cn+1 choix pour cet élément particulier. Il reste alors n éléments de {1, 2, ..., n + 1} que l’on met en bijection
n (n + 1)!
avec {1, 2, ..., n} , il y n! bijections différentes. Au total on a Cn2 × n! = surjections de {1, 2, ..., n + 1} dans
2
{1, 2, ..., n} ..

2.4. Les olympiques

1. On se donne une partie A ⊂ E à k éléments. Pour construire un couple (A, B) tel que A ∩ B = ∅, il faut choisir une
partie dans EÂA, on dispose de 2n−k choix possibles. On a donc 2n−k Cnk couples (A, B) qui satisfont à A ∩ B = ∅ tels
Xn
que Card(A) = k. Ce qui donne 2n−k Cnk = 3n couples possibles. Mais il faut enlever le couple (∅, ∅) qui n’est pas
k=0


 
Géry Huvent. Lycée Baggio. PTSI1 4

constitué de parties distinctes. Il y a 3n − 1 couples possibles.

X P P
2. On a Cnk parties à k éléments, donc Card (A) = nk=0 kCnk qui se calcule avec (1 + x)n = nk=0 Cnk xk que l’on
A⊂E
dérive pour avoir n2n−1 (cf exercice 6 (Basiques))
2
Pour la seconde somme, soit une partie C de E à k éléments. Combien y a-t-il de couples (A, B) ∈ P (E) tels que
C =A∩B?
Il faut choisir un couple (A0 , B 0 ) ∈ P (E \ C)2 tel que A0 ∩ B 0 = ∅. X P
D’après l’exercice 1 (lOlympiques), il y a 3n−k couples possibles. On a donc Card (A ∩ B) = nk=0 kCnk 3n−k =
A⊂E
B⊂E
n−1
n4 X X
EnÞn Card (A ∪ B) = Card (A) + Card (B) − Card (A ∩ B) = n2n × 2n−1 + n2n × 2n−1 − n4n−1 = 3n4n−1
A⊂E A⊂E
B⊂E B⊂E