Dénombrement

Cours de É. Bouchet  ECS1

5 novembre 2018

Table des matières

1 Techniques de dénombrement 2
2 Dénombrement des ensembles 3
2.1 p-listes d'un ensemble à n éléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 p-liste d'éléments distincts d'un ensemble à n éléments . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Permutations d'un ensemble à n éléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Parties à p-éléments d'un ensemble à n éléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Parties d'un ensemble à n éléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Coecient binomiaux 7
3.1 Dénition et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Formule de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Formule du binôme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1
1 Techniques de dénombrement
Dénition (Cardinal).
Soit A un ensemble ni. On appelle cardinal le nombre de ses éléments, et on le note Card(A).

Formule (Formule de somme).

Si A et B sont deux ensembles nis disjoints, alors

Card (A ∪ B) = Card(A) + Card(B).

Formule (Formule de somme, cas général).

Si A et B sont deux ensembles nis, alors

Card (A ∪ B) = Card(A) + Card(B) − Card (A ∩ B) .

Formule (Formule du complémentaire).

Si Ω est un ensemble ni et A ⊂ Ω, alors


Card A = Card(Ω) − Card(A).

Démonstration. En eet, A ∪ A = Ω, et A et A sont disjoints, on peut donc appliquer la formule de somme :

Card A + Card(A) = Card(Ω).

Formule (Formule de partition).

n
Soit n ∈ N∗ . Soit Ω un ensemble ni et (Ai )i∈[[1,n]] une famille de sous-ensembles de Ω vériant
[
Ai = Ω
i=1
et tels que pour tout i 6= j , Ai ∩ Aj = ∅, (on parle alors d'ensembles disjoints deux à deux). Alors
n
X
Card(Ω) = Card(Ai ).
i=1

Démonstration. Soit n ∈ N∗ , on pose :

n n
P (n) :  ∀(Ai )i∈[[1,n]] ∈ P(Ω)n , si Ai = Ω et ∀i 6= j, Ai ∩ Aj = ∅, alors Card(Ω) = Card(Ai ) .
[ X

i=1 i=1

2
 1
 Pour n = 1, si A1 = Ω, Card(Ω) = Card(A1 ) = Card(Ai ) donc P (1) est vraie.
X

i=1
 Soit n ∈ N∗ , on suppose que P (n) est vraie. Soit (Ai )i∈[[1,n+1]] ∈ P(Ω)n+1 , on suppose que n+1 i=1 Ai = Ω et que
S
∀i 6= j , Ai ∩ Aj = ∅. Alors (A1 , . . . , An−1 , (An ∪ An+1 )) vérie les hypothèses de P (n), on a donc :
n−1
X
Card(Ω) = Card(Ai ) + Card(An ∪ An+1 ).
i=1

Or An ∩ An+1 = ∅, donc par formule de somme, Card(An ∪ An+1 ) = Card(An ) + Card(An+1 ). Donc P (n + 1)
est vraie.
D'où le résultat.
Formule (Formule du produit).
Si A et B sont deux ensembles nis, alors

Card (A × B) = Card(A) × Card(B).

2 Dénombrement des ensembles

2.1 p-listes d'un ensemble à n éléments
Dénition (p-liste).

Soit (p, n) ∈ (N∗ )2 . Soit E un ensemble ni de cardinal n. On appelle p-liste de E tout élément de E p .

Exemple 1. (1, 2, 1) est une 3-liste d'éléments de l'ensemble [[1, 6]] de cardinal 6.

Proposition (Nombre de p-listes).

Soit (p, n) ∈ (N∗ )2 . Le nombre de p-listes d'un ensemble à n éléments est Card (E p ) = np .

Démonstration. Par la formule du produit, itérée p − 1 fois, on trouve Card (E p ) = Card(E)p = np .

Représentation arborescente : Les 3-listes de [[1, 4]].

1 2 3 4

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

1234 1234 1234 1234 1234 1234 1234 1234 1234 1234 1234 1234 1234 1234 1234 1234

Il y en a au total 43 = 64.

3
Exemple 2. On tire trois cartes avec remise dans un jeu de 32 cartes. Combien de tirages diérents peut-on rencontrer ?
Un tirage de trois cartes avec remise est une 3-liste d'un ensemble à 32 éléments : il y a donc 323 = 32768 possibilités.

2.2 p-liste d'éléments distincts d'un ensemble à n éléments

Dénition (p-liste d'éléments distincts).
Soit E un ensemble ni de cardinal n ∈ N∗ et soit p ∈ [[1, n]]. On appelle p-liste d'éléments distincts
de E tout élément (x1 , . . . , xp ) ∈ E p tel que

∀(i, j) ∈ [[1, p]]2 tels que i 6= j, xi 6= xj .

Exemple 3. (1, 2, 5) est une 3-liste d'éléments distincts de l'ensemble [[1, 6]] de cardinal 6.

Proposition (Nombre de p-listes d'éléments distincts).

Soit n ∈ N∗ et p ∈ [[1, n]]. Le nombre de p-listes d'éléments distincts d'un ensemble à n éléments est
n!
Apn = .
(n − p)!

Remarque. Une p-liste d'éléments distincts est également appelée un arrangement de p parmi n ou une p-liste sans
répétition.

Représentation arborescente : Les 3-listes d'éléments distincts de [[1, 4]].

On élague des branches de la représentation des 3-listes :
1 2 3 4

2 3 4 1 3 4 1 2 4 1 2 3

34 2 4 23 34 1 4 1 3 2 4 1 4 12 23 1 3 12
4! 4×3×2
Il y en a au total A34 = = = 24.
(4 − 3)! 1
Exemple 4. On tire trois cartes sans remise dans un jeu de 32 cartes. Combien de tirages diérents peut-on rencontrer ?
Un tirage de trois cartes sans remise est une 3-liste d'éléments distincts d'un ensemble à 32 éléments : il y a donc
32!
A332 = = 32 × 31 × 30 = 29760 possibilités. On peut vérier que ce résultat est cohérent : il est bien plus
(32 − 3)!
petit que dans le cas avec remise.

4
2.3 Permutations d'un ensemble à n éléments
Dénition (Permutation).
Soit A un ensemble ni. Une permutation de A est une bijection de A sur lui-même.

Remarque. Une permutation de n objets distincts rangés dans un certain ordre correspond à un changement de
l'ordre de succession de ces n objets.
Remarque. On représente souvent une permutation en donnant les images successives de ses éléments : c'est plus
rapide que de dénir explicitement la bijection utilisée.
Exemple 5. Si E = [[1, 5]], (1; 2; 3; 4; 5), (5; 4; 3; 2; 1) et (2; 4; 1; 3; 5) sont des permutations de E .
Proposition.
Soit n ∈ N∗ . Le nombre de permutations d'un ensemble à n éléments est n!.

Démonstration. Ce résultat découle directement du fait que si E est un ensemble à n éléments, une permutation de
E est une n-liste d'éléments distincts de E . Il y en a donc Ann = n!
0! = n!.

Représentation arborescente : Les permutations de [[1, 4]].

1 2 3 4

2 3 4 1 3 4 1 2 4 1 2 3

3 4 2 4 2 3 3 4 1 4 1 3 2 4 1 4 1 2 2 3 1 3 1 2

4 3 4 3 3 2 4 3 4 1 3 1 4 2 4 1 2 1 3 2 3 1 2 1

Il y en a au total 4! = 24.
Exemple 6. De combien de manières diérentes peut-on mélanger un jeu de 32 cartes ?
Le nombre de mélanges correspond au nombre de permutations sur les 32 cartes : il y en a 32! (de l'ordre de 1035 ...)
Exemple 7. Combien PERLE a-t-il d'anagrammes ?
Ce mot a 5 lettres, il y a donc a priori 5! façon de les mélanger. Mais la lettre E gure deux fois : intervertir les deux
lettres E ne modie pas le mot. Il y a donc 2! 5!
= 60 anagrammes.

2.4 Parties à p-éléments d'un ensemble à n éléments

Dénition (Parties à p-éléments d'un ensemble à n éléments).
Soit E un ensemble ni de cardinal n ∈ N et soit p ∈ [[0, n]]. On appelle partie à p éléments de E tout
sous-ensemble de E à p éléments.

5
Exemple 8. {1, 2, 5} est une partie à 3 éléments de l'ensemble [[1, 6]] de cardinal 6.

Proposition (Nombre de parties à p-éléments d'un ensemble à n éléments).

Soit n ∈ N et p ∈ [[0, n]]. Soit E un ensemble ni de cardinal n. Le nombre de parties à p-éléments de E est
 
n n!
= .
p p! (n − p)!

Représentation arborescente Les parties à p éléments d'un ensemble à n éléments peuvent être vues comme le
nombre de chemins d'un arbre réalisant p succès pour n répétitions. Par exemple, pour p = 2 et n = 3 :

1 •
1 •
0 • ←− 2 victoires
•
1 1 • ←− 2 victoires
0 •
0 •
•
1 • ←− 2 victoires
1 •
0 0 •
•
1 •
0 •
•
 
3 3×2
0 Il y en a au total = = 3.
2 2

Exemple 9. On tire simultanément trois cartes dans un jeu de 32 cartes. Combien de tirages diérents peut-on
rencontrer ?
Un tirage simultané de trois cartes est une partie à 3 éléments d'un ensemble à 32 éléments : il y a donc 32


3 =
32×31×30
3! = 4960 possibilités. C'est beaucoup moins que le nombre de 3 -listes d'éléments distincts, car l'ordre dans
lequel on pioche les cartes ne compte pas.

2.5 Parties d'un ensemble à n éléments

Proposition (Parties d'un ensemble à n éléments).
Soit n ∈ N et E un ensemble ni de cardinal n. Le nombre de parties de E est

Card (P (E)) = 2n .

Démonstration. (démonstration à connaître) Soit n ∈ N, on pose P (n) =  si E est un ensemble ni de cardinal n,
Card (P (E)) = 2n .
 Le seul ensemble de cardinal 0 est ∅, et le P (∅) = {∅} est de cardinal 1 = 20 . Donc P (0) est vraie.
 Soit n ∈ N on suppose que P (n) est vraie. Soit E un ensemble ni de cardinal n + 1, et soit x ∈ E (existe car
Card(E) > 1). Alors E = {x} ∪ E 0 , où E 0 est un ensemble ni de cardinal n. Soit A ∈ P(E). Alors :
 Soit x ∈/ A et A ∈ P (E 0 ).
 Soit x ∈ A et on peut écrire A = {x} ∪ B avec B ∈ P (E 0 ).

6
 Ces deux possibilités sont disjointes. Donc le nombre de parties de E est le nombre de parties contenant x, plus
le nombre de parties ne le contenant pas. Dans les deux cas, cela vaut 2n par P (n). Il y en a donc 2n +2n = 2n+1 .
Donc P (n + 1) est vraie.
D'où le résultat annoncé.

3 Coecient binomiaux
3.1 Dénition et propriétés
Dénition (Coecient binomiaux).
Soit (n, p) ∈ Z2 .  
n n!
 Si n ∈ N et p ∈ [[0, n]] on pose = .
p
  p! (n − p)!
n
 Si n < 0 ou p ∈
/ [[0, n]] on pose = 0.
p

 
8 8×7×6×5
Exemple 10. = = 70.
4 1×2×3×4

Formule.
∀(n, p) ∈ Z2 ,    
n n
= .
p n−p

     
8 8 8
Exemple 11. = = .
2 8−2 6
   
n n! n
Démonstration. Si n ∈ N et p ∈ [[0, n]], alors n − p ∈ [[0, n]], et la dénition donne : = = .
n−p (n − p)!p! p
Sinon, les deux termes sont nuls. Dans tous les cas, il y a donc égalité.
Formule.
Soit n ∈ Z. ∀p ∈ Z∗ ,    
n n n−1
= ,
p p p−1
∀p ∈ Z \ {0, 1},    
n n(n − 1) n − 2
= .
p p(p − 1) p − 2

Dé[Link] va montrer la première

  formule, la deuxième s'obtient simplement en itérant la première.
 
n n! p>1,n>1 n (n − 1)! n n−1
 Si n > 1 et p ∈ [[1, n]], on a : = = = , où la
p p! (n − p)! p (p − 1)! ((n − 1) − (p − 1))! p p−1
dernière égalité est valide car on a bien p − 1 ∈ [[0, n − 1]].
 Sinon les deux termes sont nuls.
On a donc bien toujours égalité.

7
3.2 Formule de Pascal
Remarque (Représentation ensembliste). Parties à p éléments d'un ensemble à n éléments.
Soit n ∈ N∗ , p ∈ [[1, n − 1]] et E un ensemble ni de cardinal n. On sait qu'il y a np possibilités d'obtenir une partie

à p éléments de E . Mais pour construire une telle partie à p éléments, on peut aussi
écrire E = E 0 ∪ {x} puis :
 soit on ne choisit pas x, et on choisit p éléments parmi les n − 1 de E 0 : n−1p possibilités,
 soit on choisit x, et on choisit ensuite p − 1 éléments parmi les n − 1 de E : p−1 possibilités,
0 n−1

ces deux cas étant disjoints. D'où np = n−1 p−1 .

+ n−1




p

Formule (Formule de Pascal).

∀(n, p) ∈ Z2 \ {(0, 0)},      
n n−1 n−1
= + .
p p p−1

Démonstration. (démonstration à connaître) Si n ∈ N∗ et p ∈ [[1, n − 1]], on a aussi p − 1 ∈ [[0, n − 1]] et :

   
n−1 n−1 (n − 1)! (n − 1)!
+ = +
p p−1 p! (n − 1 − p)! (p − 1)! ((n − 1) − (p − 1))!
 
(n − 1)! p
= 1+
p! (n − 1 − p)! n−p
 
(n − 1)! n
=
p! (n − 1 − p)! n − p
 
n
=
p

Si n ∈ N∗ et p = 0, n−1 + n−1 n−1

+ 0 = 1 = n0 . Si n ∈ N∗ et p = n, n−1 n−1 n
. Dans








0 −1 = 0 n + n−1 =0+1=1= n
tous les autres cas, les deux membres de la formule sont nuls dont égaux.
La formule est donc vraie pour tout couple d'entiers diérent de (0, 0).

Corollaire.
 
n
∀n ∈ N, ∀p ∈ [[0, n]], ∈ N.
p

 
n
Démonstration. Soit n ∈ N, on pose P (n) =  ∀p ∈ [[0, n]], ∈ N .
  p
0
 Initialisation : si n = 0, = 1 ∈ N. Donc P (0) est vraie.
0
 Soit n ∈ N xé. Supposons que P (n) est vraie. Soit p ∈ [[0, n + 1]]. Alors par la formule de Pascal,
     
n+1 n n
= + .
p p p−1

Si p ∈ [[1, n − 1]], P (n) garantit que les deux termes de cette somme sont entiers. Par ailleurs, si p = 0, n


p−1 =0
et np ∈ N et si p = n + 1, p−1 n
∈ N et np = 0. Donc P (n + 1) est vraie.

Cela montre le résultat annoncé.

8
Remarque. Le tableau suivant, appelé triangle de Pascal, permet de retrouver facilement les petits coecients
binomiaux :

n\p 0 1 2 3 4 5
0 1 0 0 0 0 0
1 1 1 0 0 0 0
2 1 2 1 0 0 0
3 1 3 3 1 0 0
4 1 4 6 4 1 0
5 1 5 10 10 5 1

3.3 Formule du binôme de Newton

Formule (Formule du binôme de Newton).
∀(a, b) ∈ R2 , ∀n ∈ N,
n  
n
X n k n−k
(a + b) = a b
k
k=0

n  
n
(démonstration à connaître) Soit n ∈ N, on pose P (n) : (a + b) = ak bn−k .
n
X
Démonstration.
k
k=0
0    
n k n−k 0 0 0
 (a + b) = 1, et a b = 1 donc P (0) est vraie.
0
X
a b =
k 0
k=0
 Soit n ∈ N, supposons que P (n) est vraie. Alors :
n  
n k n−k
Par P (n)
n+1
X
(a + b) = (a + b) a b
k
k=0
n   n  
X n k+1 n−k X n k n−k+1
= a b + a b
k k
k=0 k=0
n+1
X n  n  
n k n−k+1
en posant k0 = k + 1
X
k n−k+1
= a b + a b
k−1 k
k=1 k=0
n    
n n
en séparant k = 0, n + 1
X
n+1 n+1
=a +b + + ak bn−k+1
k−1 k
k=1
n  
n + 1 k n−k+1
par la formule de Pascal
X
= an+1 + bn+1 + a b
k
k=1

Donc P (n + 1) est vraie.

Cela montre le résultat annoncé.
Exemple 12. Soit x ∈ R. Calculer (1 + x)4 .
La formule du binôme de Newton donne :
         
4 4 4 4 3 4 2 4 4 4
(1 + x) = x + x + x + x+ x = x4 + 4x3 + 6x2 + 4x + 1.
0 1 2 3 4

9
 n  
n
Exemple 13. Calculer puis donner une interprétation ensembliste de ce résultat en lien avec le cardinal de
X
k
k=0
P(E).
La formule du binôme de Newton donne :
n   n  
X n X n
= 1k 1n−k = (1 + 1)n = 2n .
k k
k=0 k=0

Interprétation ensembliste : soit E un ensemble de cardinal n. Pour choisir un élément de P(E), on peut :
 commencer par choisir son cardinal k ∈ [[0, n]],
 choisir ensuite les k éléments qui le composent, parmi les n = Card(E) éléments possibles : il y a nk possibilités

pour faire ce choix lorsque k est xé.   n

n
Ces possibilités correspondent à des cas disjoints, il y a donc possibilités pour choisir un élément de P(E).
X
k
k=0
Ce nombre correspond donc au cardinal de P(E), dont on a déjà déterminé qu'il valait 2n .
n  
n
Exemple 14. Soit n ∈ N∗ .
Calculer .
X
k
k
k=0

On sait que pour tout entier k non nul, nk = nk n−1
. Donc


k−1
n   n   n   n−1  
X n X n X n − 1 i=k−1 X n − 1
k =0+ k =n = n = n2n−1 ,
k k k−1 i
k=0 k=1 k=1 i=0

où la dernière égalité utilise la formule du binôme de Newton.

  X p   
a+b a b
Exemple 15. Soit (a, b) ∈ N2 et p ∈ [[0, a + b]]. Montrer la formule de Vandermonde : = .
p k p−k
k=0
Première possibilité de preuve : preuve ensembliste. On cherche à choisir astucieusement p éléments dans un ensemble
E contenant a + b éléments. On écrit E = A ∪ B , où Card(A) = a et Card(B) = b, et on procède comme suit :
 on commence par choisir le nombre k ∈ [[0, p]]
d'éléments à choisir dans A,
 à k xé, on choisit les k éléments dans A : ka possibilités,
 on complète ensuite avec p − k éléments de B : p−k b
possibilités.


p
X a   
b
On a donc par formule de somme (cas disjoint) possibilités de faire ce choix. D'où le résultat.
k p−k
k=0
Deuxième possibilité de preuve : preuve algébrique. On s'intéresse au polynôme (1 + X)a+b = (1 + X)a (1 + X)b . La
formule du binôme de Newton donne :
a+b   a  
! b   
X a+b X a X b
Xp = Xi  Xj .
p i j
p=0 i=0 j=0

On va chercher à développer le membre de droite, pour pouvoir identier les coecients du polynôme : pour cela, on
commence par déterminer les exposants qui apparaîtront dans le produit, puis on détermine leurs coecients :
a  
!  b    a+b  
p  
a+b X !
X a X b X X ab X a b
Xi  Xj =   Xp = X p,
i j i j k p−k
i=0 j=0 p=0 i+j=p p=0 k=0

En identiant les coecients, on trouve ∀p ∈ [[0, a + b]],

  Xp   
a+b a b
= .
p k p−k
k=0

10