Dénombrement

ECE1 Lycée Kastler

31 janvier 2008

Introduction
La combinatoire, science du dénombrement, sert comme son nom l'indique à compter. Il ne s'agit
bien entendu pas de revenir au stade du CP et d'apprendre à compter sur ses doigts, mais bien de
dénir des oblets mathématiques permettant de compter le nombre d'éléments d'ensemble bien trop
gros et compliqués pour être dénombrés à la main.
Quelques exemples de problèmes faisant intervenir les objets que nous allons étudier dans ce
cours :
• Dix personnes assistent à un diner autour d'une table ronde. Combien y a-t-il de façons de
disposer les dix convives autour de la table ? Si de plus on impose que deux de ces convives, qui
ne s'apprécient guère, ne doivent pas être placée côte à côte, combien reste-t-il de dispositions
possibles ?
• Il y a 41 élèves dans la classe. Quelle est la probabilité qu'il y en ait (au moins) deux parmi
eux qui soient nés le même jour de l'année ?
• Pour remplir une grille de loto, on coche six numéros parmi les nombres compris entre 1 et
49. De combien de façons peut-on remplir une telle grille ? Question subsidiaire : quelle est la
probabilité de gagner au loto ?
Le mot probabilité apparait deux fois dans les premiers exemples donnés ci-dessus. Les probabi-
lités (que nous commencerons à étudier très bientôt) sont en eet étroitement liées aux problèmes
de dénombrement, puisque calculer une probabilité dans le cadre des probabilités nies revient es-
sentiellement à dénombrer les cas favorables. Il faut toutefois se méer, bien dénombrer étant parfois
plus compliqué qu'on ne pourrait le penser, comme le prouve le classique exemple suivant : on lance
simultanément trois dés et on note la somme des trois chires obtenus. A-t-on plus de chances d'ob-
tenir 9 ou 10 ? On pourrait penser que les deux sommes sont aussi probable par le raisonnement
suivant : il y a 6 façons d'obtenir 9 (1 + 2 + 6, 1 + 3 + 5, 1 + 4 + 4, 2 + 2 + 5, 2 + 3 + 4 et 3 + 3 + 3) et
également 6 façons d'obtenir 10 (1 + 3 + 6, 1 + 4 + 5, 2 + 2 + 6, 2 + 3 + 5, 2 + 4 + 4 et 3 + 3 + 4). On
observe pourtant expérimentalement que le 10 revient sensiblement plus souvent que le 9. Cela est
du fait que chacune des possibilités dénombrées ci-dessus n'a pas la même probabilité d'apparition :
obtenir trois 3 est beaucoup moins probable qu'obtenir trois chires diérents (six fois moins).

1 Cardinaux d'ensembles nis

1.1 Quelques dénitions
Dénition 1. Un ensemble E est dit ni s'il existe un entier naturel n tel que E soit en bijection
avec {1; 2; . . . ; n}. Cet entier n est alors unique
Dénition 2. L'entier n est appelé cardinal de l'ensemble E et noté |E|, ou card(E), ou encore #E
Remarque 1. Cela correspond bien à la notion intuitive d'ensemble dont on peut compter les éléments.
En eet, une bijection de E vers {1; . . . ; n} est simplement une façon d'étiquetter les éléments de E
avec les numéros 1, 2, . . ., n.

1
Remarque 2. Si E est un ensemble qui n'est pas ni, il existe une injection de N dans E (mais pas

forcément une bijection, mais ce dernier points est une histoire compliquée que nous laisserons de
côté).
Proposition 1. Soit E un ensemble ni et F un sous-ensmble de E , alors F est un ensemble ni,
et |F | 6 |E|, avec égalité si et seulement si E = F .
Démonstration. Cette propriété, comme souvent en ce qui concerne les ensembles nis, est assez

évidente d'un point de vue intuitif, mais pas si simple à démontrer correctement. Nous nous en
tiendrons au point de vue intuitif.
Proposition 2. Soit E et F deux ensembles nis. Alors si E et F sont en bijection l'un avec l'autre,
ils ont même cardinal.
Démonstration. Il existe par hypothèse une bijection f de E vers F . De plus, F étant ni, notons n

son cardinal, il existe alors une bijection g de F dans {1; . . . ; n}. L'application g ◦ f : E → {1; . . . ; n}
est une composée d'applications bijectives, donc est bijective, ce qui prouve que E est de cardinal
n.

1.2 Cardinaux élémentaires

Proposition 3. Soient A et B deux sous-ensembles d'un même ensemble ni E . Alors |A ∪ B| =
|A| + |B| − |A ∩ B|.
Démonstration. Commençons par constater que dans le cas où les deux ensembles A et B sont

disjoints, on a |A ∪ B| = |A| + |B|. Vous voulez une démonstration ? Soit f une bijection de A dans
{1; . . . ; p} et g une bijection de B dans {1; . . . ; q}, p et q étant les cardinaux respectifs de A et de B .
On peut alors construire une bijection h de A ∪ B vers {1. . . . ; p + q} en posant ∀x ∈ A, h(x) = f (x)
et ∀x ∈ B , h(x) = g(x) + p. Une fois ce fait admis, constatons que A ∪ B est l'union disjointe des
trois ensembles A\B , B\A et A ∩ B . On a donc |A ∪ B| = |A\B| + |B\A| + |A ∩ B|. Or, A étant union
disjointe de A\B et de A ∩ B , on a également |A| = |A\B| + |A ∩ B|, ou encore |A\B| = |A| − |A ∩ B|.
De même, |B\A| = |B| − |A ∩ B|, donc on obtient |A ∪ B| = |A| − |A ∩ B| + |B| − |A ∩ B| + |A ∩ B|,
ce qui donne bien la formule annoncée.
Théorème 1. Formule du crible de Poincaré.
Soient A1 , A2 , . . ., An des sous-ensembles nis d'un même ensemble E , alors
n
n X X
| ∪ Ai | = |Ai1 ∩ · · · ∩ Aik |
i=1
k=1 16i1 <···<ik 6n

Proposition 4. La formule de Poincaré étant assez peu lisible, voici ce que ça donne pour n = 3 et
n=4:
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
|A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D| − |A ∩ B| − |A ∩ C| − |A ∩ D| − |B ∩ C| − |B ∩ D| − |C ∩
D| + |A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D| − |A ∩ B ∩ C ∩ D|
Démonstration. La preuve de la formule générale, assez technique, se fait par récurrence. On se

contentera de prouver la formule pour n = 3 en partant de la proposition précédente : |A ∪ B ∪ C| =

|(A ∪ B) ∪ C| = |A ∪ B| + |C| − |(A ∪ B) ∩ C| = |A| + |B| − |A ∩ B| + |C| − |(A ∩ C) ∪ (B ∩ C)| =
|A| + |B| − |A ∩ B| + |C| − |A ∩ C| − |A ∩ B| + |A ∩ C ∩ B ∩ C|, ce qui donne bien la formule
annoncée.
Exemple : Dans un lycée de 300 élèves, 152 pratiquent le football, 83 le rugby et 51 le tennis.
De plus, 24 pratiquent à la fois foot et rugby, 14 font foot et tennis, et 8 rugby et tennis. Enn, 3
élèves pratiquent les trois sports simultanément. Le nombre d'élèves sportifs est alors de 152 + 83 +
51 − 24 − 14 − 8 + 3 = 237.

2
Proposition 5. Soit A un sous-ensemble ni d'un ensemble ni E , alors |Ā| = |E| − |A|.
Démonstration. C'est une conséquence de la formule pour une union : E est union disjointe de A et
de Ā.
Proposition 6. Soient A et B deux ensembles nis, alors A × B est ni, et |A × B| = |A| × |B|.
Démonstration. Pas de preuve rigoureuse pour celui-ci, simplement une idée de la façon dont ça

marche. Soit n le cardinal de A, et e1 , e2 , . . . , en ses éléments, p le cardinal de B et f1 , . . . , fp ses

éléments. on peut placer les éléments de A × B dans un tableau de la façon suivante :
e1 e2 ... en
f1 (e1 , f1 ) (e2 , f1 ) . . . (en , f1 )
.. .. .. ... ..
. . . .
fp (e1 , fp ) (e2 , fp ) . . . (en , fp )
Il y bien n × p éléments dans le tableau, donc dans A × B .

2 Listes, arrangements et combinaisons

Dénition 3. Soit E un ensemble ni de cardinal n, et p ∈ N∗ . Une p-liste d'éléments de E , ou
p-uplet d'éléments de E , est simplement un élément de E p .
Remarque 3. On peut très bien avoir plusieurs fois le même élément dans une p-liste. Par ailleurs,

l'ordre des éléments de la p-liste est important.

Proposition 7. Le nombre de p-listes dans un ensemble de cardinal n vaut np .
Démonstration. C'est une conséquence de la formule de cardinal du produit vue un peu plus haut :

comme |A × B| = |A| × |B|, on a |E p | = |E|p , ce qui prouve bien la propriété.

Exemple : Dans une urne se trouvent 10 boules numérotées de 1 à 10. On tire quatre succes-
sivement avec remise. Un tel tirage revient à choisir une 4-liste dans l'ensemble à 10 éléments
constitué des entiers de 1 à 10. Il y a donc 104 = 10 000 tirages possibles.
Remarque 4. Le nombre de p-listes d'un ensemble à n éléments est aussi le nombre d'applications

de l'ensemble {1; . . . ; p} vers cet ensemble. En eet, se donner une telle application f revient à se
donner les valeurs des images f (1), f (2), . . ., f (p), c'est-à-dire à se donner p éléments de E .
Dénition 4. Soit E un ensemble à n éléments et p ∈ N∗ , on appelle arrangement de p éléments de
E une p-liste d'éléments distincts de E .
Remarque 5. L'ordre des éléments est toujours important, par contre on ne peut plus avoir de
répétition d'élément dans un arrangement.
n!
Dénition 5. Soient n et p deux entiers tels que p 6 n, on note An,p = = n(n − 1)(n −
(n − p)!
2) . . . (n − p + 1).
Proposition 8. Le nombre d'arrangements de p éléments dansun ensemble à n éléments vaut An,p .
Démonstration. Idée de démonstration : lorsqu'on construit un arrangement, on a n choix pour le

premier élément, n−1 pour le deuxième, . . ., n−p+1 pour le pème, soit au total n(n−1)×(n−p+1) =
n(n − 1) . . . (n − p + 1)(n − p) . . . 2 × 1 n!
= .
n(n − 1) . . . 2 × 1 (n − p)!
Exemple : Si on reprend notre urne avec ses 10 boules et qu'on en tire désormais quatre suc-
10!
cessivement sans remise, on construit des arrangements, et il y a = 5040 tirages possibles.
6!

3
Remarque 6. Le nombre d'arrangements de p éléments dans un ensemble à n éléments est également
le nombre d'application injectives de {1; . . . ; p} dans E .
Dénition 6. Un arrangement de n éléments dans un ensemble à n éléments est aussi appelé
permutation. Il y a donc n! permutations dans un ensemble à n éléments.
Exemple : Le nombre d'anagrammes d'un mot peu se calculer à l'aide de permutations. Il faut
simplement diviser le nombre total du permutations du mot par k chaque fois qu'une même lettre
apparait k fois dans le mot. Par exemple, le nombre d'anagrammes du mot DENOMBREMENT est
12!
.
3! × 2! × 2!
Remarque 7. Le nombre de permutations d'un ensemble à n éléments est le nombre d'applications
bijectives de cet ensemble dans lui-même.
Dénition 7. Une combinaison de k éléments dans un ensemble ni E à n éléments est un sous-
ensemble à k éléments de E .
Dénition
 8. Soient n et k deux entiers tels que k 6 n, on appelle coecients binomiaux les
n n!
nombres = . Ce nombre est également noté Cnk .
k k!(n − k)!
 
n
Remarque 8. On pose souvent = 0 si k > n.
k
 
n
Proposition 9. Le nombre de sous-ensembles à p éléments d'un ensemble à n éléments est .
p
Démonstration. En eet, une combinaison n'est rien d'autre qu'un arrangement dans lequel on a en-
levé l'importance de l'ordre. Autrement dit, chaque combinaison apparait p! fois quand on dénombre
les arrangements (puisqu'il y a p! façonsd'ordonner
 un ensemble à p éléments), donc le nombre de
An,p n
combinaisons à p éléments vaut = .
p! p
Exemple : Toujours dans notre
  urne avec ses dix boules, on tire désormais quatre boules simul-
10
tanément. Il y a maintenant = 210 tirages possibles.
4
Remarque 9. On peut encore une fois interpréter ceci à l'aide d'applications : le nombre de combinai-
sons à p éléments dans un ensemble à n éléments est le nombre d'applications strictement croissantes
de {1; . . . ; p} dans E . En eet, se donner une application strictement croissante f est équivalent à
se donner le sous-ensemble {f (1); f (2), . . . ; f (p)}.

3 Propriétés des coecients binomiaux

Proposition
  10. Quelques
 propriétés
 des coecients binomiaux, utiles pour les calculs :
n n n n(n − 1)
• = 1; = n; = .
0  1  2
 2
n n
• ∀k 6 n, = (propriété de symétrie).
k  n − k 
n n−1
• ∀1 6 k 6 n, k =n
 k  k − 1   
n−1 n−1 n
• ∀1 6 k 6 n, + = (relation de Pascal).
k k−1 k

4
Démonstration.
  Pour
 le premier point, il sut
 de reprendre la dénition des coecients binomiaux :
n n! n n! n n! n(n − 1)
= = 1; = = n et = = .
0 0!n! 1 (n − 1)! 2
 2!(n
 − 2)! 2  
n n! n! n
La propriété de symétrie est facile aussi : = = = .
n−k (n − k)!(n − (n − k))! (n − k)!k! k
Il y a également une interprétation combinatoire de ce résultat : choisir un sous-ensemble de k
éléments dans un ensemble à n éléments est équivalent à choisir son complémentaire, qui est contitué
de n − k éléments, donc  ily a autant de sous-ensembles à k éléments  età n − k éléments.
n k × n! n! n−1 n × (n − 1)!
Pour la troisième, k = = , et n = =
k k!(n − k)! (k − 1)!(n − k)! k−1 (k − 1)!(n − 1 − k + 1)!
n!
, les deux quantités sont bien égales.
(k − 1)!(n − k)!    
n−1 n−1 (n − 1)! (n − 1)!
Enn, la formule de Pascal : + = +
k k−1  −
k!(n  1 − k)! (k − 1)!(n − k)!
(n − k) × (n − 1)! + k × (n − 1)! n × (n − 1)! n
= = = . La encore, il y a une interprétation
k!(n − k)! k!(n − k)! k
combinatoire.  Soit E un ensemble à n éléments et x ∈ E . Les sous-ensembles de E à k éléments,
n
au nombre de , se répartissent en deux catégories : ceux qui contiennent x, qui sont au nombre
  k
n−1
de puisqu'il reste k − 1 à choisir parmi les n − 1 restant dans E une fois x choisi ; et ceux
k−1  
n−1
qui ne contiennent pas x, qui sont au nombre de puisqu'il reste cette fois-ci k éléments à
k
choisir parmi les n − 1 restants (on n'en a encore choisi aucun). D'où la formule.
Triangle de Pascal : La relation de Pascal permet de calculer les valeurs des coecients bino-
miaux par récurrence, en les répartissant sous forme d'un tableau triangulaire :
k=0 k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8
n=0 1
n=1 1 1
n=2 1 2 1
n=3 1 3 3 1
n=4 1 4 6 4 1
n=5 1 5 10 10 5 1
n=6 1 6 15 20 15 6 1
n=7 1 7 21 35 35 21 7 1
n=8 1 8 28 56 56 56 28 7 1
Pour obtenir un coecient du tableau, on fait la somme de celui qui est au-dessus de lui, et de
celui qui est à gauche de celui-ci.
Théorème 2. Formule du binôme de Newton. n  
n
Soient a et b deux réels, et n ∈ N, alors (a + ak bn−k .
X
b)n =
k
k=0

Remarque 10. On peut obtenir à partir de cette formule le développement d'une diérence : (b−a)n =
n  
n
(−1)k ak bn−k . En pratique, il sut d'alterner les signes.
X
k
k=0
Exemple : (a + b)6 = a6 + 6a5 b + 15a4 b2 + 20a3 b3 + 15a2 b4 + 6ab5 + b6 . L'ordre est inversé
par rapport à celui de la formule, mais c'est la façon habituelle d'écrire le développement. Autre
exemple : (1 − x)5 = 1 − 5x + 10x2 − 10x3 + 5x4 − x5 .

5
Démonstration. On va procéder 
parrécurrence sur l'entier n. Pour n = 0, la formule du binome
0 0 0
dit simplement que (a + b)0 = a b , ce qui est vrai (on a 1 de chaque côté). Supposons la
0
n  
n
formule vraie au rang n, on a alors (a + ak bn−k par
X
b)n+1 = (a + b)(a + b)n = (a + b)
k
k=0
hypothèse de récurrence, donc en développant lea + b et en le faisant rentrer dans la somme, on
n  n
n n k n+1−k
obtient (a + b)n+1 = . Eectuons un changement d'indice en
X X
ak+1 bn−k + a b
k k
k=0 k=0
remplaçant k par k + 1 dans la première somme (on ne touche à rien dans la deuxième) : (a + b)n+1 =
  n     n    
X
n+1 n k n+1−k
X n k n+1−k n n+1 0 X n n
k=1 a b + a b = a b + + ak bn+1−k +
k−1 k n k−1 k
  k=0 k=1
n 0 n+1
a b (on a isolé un terme dans chaque somme pour pouvoir regrouper les sommes). Mainte-
0
n+1
X n + 1
nant, on reconnait la formule de Pascal dans la somme, donc (a+b)n+1 =an+1 + ak bn+1−k +
k
k=1
bn+1 . Il ne reste plus qu'à remettre les deux termes isolés dans la somme pour obtenir la formule au
rang n + 1, ce qu'on peut faire puisqu'ils sont justement égaux aux termes manquants pour k = 0 et
k = n + 1.

Proposition 11. Formule de Leibniz

Soient f et gdeux fonction de classe C n sur un intervalle I , alors f g est aussi de classe C n sur I ,
n
X n 
et (f g)(n) = f (k) g (n−k) .
k
k=0

Démonstration. C'est la même que pour la formule du binome, on s'en passera.

Exemple : Pour n = 3, on obtient (f g)(3) = f (3) g + 3f 00 g0 + 3f 0 g00 + g(3) .
Proposition 12. Soit E un ensemble ni de cardinal n. Alors P(E) est ni, de cardinal 2n .
Démonstration. Le cardinal de P(E) est le nombre de sous-ensembles de E . Or, on sait que, pour tout
  n  
n n
entier k, il y a sous-ensembles de E à k éléments, ce qui fait au total sous-ensembles.
X
k k
k=0
Cette somme n'est rien d'autre qu'un cas particulier de formule du binôme, pour a = b = 1, donc
elle vaut (1 + 1)n = 2n .
Une façon plus combinatoire de voir les choses : à chaque sous-ensemble A de E , on peut associer
une application de E dans {0; 1} appelée application caractéristique de A, et habituellement notée
χA , dénie comme suit : si x ∈ A, χA (x) = 1 et sinon χA (x) = 0. Cette application caractérise eec-
tivement le sous-ensemble, et toute application de E dans {0; 1} est une application caractéristique
d'un sous-ensemble de E . Comme il y a 2n applications de E dans {0; 1} (cf la remarque après la
dénition des p-listes), il y a aussi 2n sous-ensembles de E .
Proposition 13. Formule de Vandermonde.   n   
a+b a b
Soient a, b et n trois entiers tels que n 6 a + b, alors .
X
=
n k n−k
k=0

Démonstration. On va passer par une interprétation combinatoire. Considérons un groupe constitué

 
a+b
de a hommes et b femmes, parmi lesquels on veut choisir n personnes. On sait déjà qu'il y a
n
possibilités de faire ce choix (ce qui correspond au membre de gauche de notre inégalité). mais on
peut également classer les groupes de n personnes
 en catégories selon le nombre d'hommes qu'ils
a b
contiennent : soit 0 homme et n femmes (il y a tels groupes), soit 1 homme et n − 1 (il y a
0 n

6
     
a b a b
tels groupes), etc, jusqu'à la possibilité d'avoir n hommes et 0 femme (il y a
1 n−1 n 0
n   
a b
tels groupes). Le nombre total de groupes possibles vaut donc aussi .
X
k n−k
k=0