Chapitre I

Combinatoire

La combinatoire (ou analyse combinatoire) est l’étude et, plus en particulier, le dénom-
brements des configurations d’une collection finie d’objets. Par exemple, voici des questions
typiques qui peuvent être resolues à l’aide de la combinatoire :
– Quel est le nombre de parties d’un ensemble de n éléments ayant exactement k élé-
ments ?
– Quel est le nombre des combinaisons de 6 numéros de 1 à 49 au Loto français, avec
au moins 3 numéros gagnants ?
On utilisera des résultats de combinatoire de base pour la théorie des probabilités sur les
ensembles finis.

1.1. Rappels de théorie des ensembles et des fonctions

Nous considerons une approche naïve à la théorie des ensembles : on dira que un en-
semble est une collection d’objets que l’on appèlle éléments de l’ensemble. Les ensembles
seront notés avec les lettres majuscules A, B,C . . ., exception faite des ensembles de nombres
naturels , entiers ou réels . Si a, b, c . . . appartiennent à l’ensemble A, on notera
A = {a, b, c . . .}, ou simplement a, b, c 2 A. On n’admet pas de répétition dans les éléments
d’un ensemble, par exemple les ensembles {1, 1, 2} et {1, 2} coïncident.
On utilisera les notations classiques pour la réunion A [ B, l’intersection A \ B, la diffé-
rence A\B et la différence symétrique A D B := (A[B)\(A\B) (voir Figure 1.1) de deux en-
sembles A, B. Par exemple, si A = {1, 2, 3, 4, 5, 6} et si B est l’ensemble des nombres impairs
(B ⇢ ), on aura A \ B = {1, 3, 5} et A \ B = {2, 4, 6}. Réunion et intersection s’étendent à
des collections infinies d’ensembles.

A[B A\B A\B ADB

A B A B A B A B

F IGURE 1.1. Réunion, intersection, différence et différence symétrique d’ensembles

Une partie ou sous-ensemble d’un ensemble A est un ensemble B dont les éléments ap-
partiennent à A (noté B ⇢ A). Deux ensembles A, B sont égaux si et seulement si A ⇢ B et
B ⇢ A (A est une partie de B et B est une partie de A). Un ensemble A contenant un nombre
fini d’éléments est dit fini, et le nombre de ses éléments (son cardinal) est notée |A|. Si A est
un ensemble, on appelle ensemble des parties de A l’ensemble P(A) dont les éléments sont
les parties de A. Par exemple
n o
P({1, 2, 3}) = 0, / {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} .

Si A est fini, |P(A)| = 2|A| (exercice).

Une fonction f : A ! B est dite injective si f (a1 ) = f (a2 ) implique a1 = a2 , pour tout
a1 , a2 2 A et surjective si pour tout b 2 B il existe a 2 A tel que f (a) = b. Une fonction
injective et surjective est dite bijective. Si A est B sont des ensembles finis, et f : A ! B est

4
bijective, alors |A| = |B|. L’ensemble des fonctions de A à B est noté BA ; si A, B sont des
ensembles finis, alors |BA | = |B||A| .
Un ensemble A est dit dénombrable s’il existe B ⇢ et une fonction bijective f : A ! B.
Par exemple, tout ensemble finis sont dénombrables. Soit A un ensemble, alors une col-
lection dénombrable A1 , . . . , An . . . 2 P(A) de parties de A est appélée une partition de
A si Ai \ A j = 0,/ pour tout i 6= j, et A = [i Ai := A1 [ A2 [ · · · [ An [ · · · . Par exemple
{1, 2, 3}, {4}, {5, 6, 7} est une partition (finie) de {1, 2, 3, 4, 5, 6, 7}.
Le résultat suivant est très important en combinatoire et sera utilisé dans la probabilité
sur les ensembles finis. Il permet d’exprimer le cardinal de la réunion d’une collection finie
d’ensembles, en fonction du cardinal de ces ensembles et de leurs intersections.

Théorème 1 (Principe d’inclusion-exclusion). Soient A1 , . . . , An ensembles finis. Alors

!
n
|A1 [ · · · [ An | = Â( 1)k+1 Â |Ai1 \ · · · \ Aik |
k=1 1i1 ···ik n

Le principe d’inclusion-exclusion pour n petit :

n = 2 : |A1 [ A2 | = |A1 | + |A2 | |A1 \ A2 |
n = 3 : |A1 [A2 [A3 | = |A1 |+|A2 |+|A3 | |A1 \A2 | |A1 \A3 | |A2 \A3 |+|A1 \A2 \A3 |
Explication pour le cas n = 3 (et en general pour tout n). On veut calculer |A1 [ A2 [ A3 |,
et pour faire ça on commence à additionner les cardinaux |A1 | + |A2 | + |A3 |. En faisant ça,
nous avons compté 2 fois chacune des intersections 2 à 2, et trois fois l’intersection 3 à
3. En soustrayant les intersections 2 à 2, on les a donc comptés une fois chacune, mais on
a soustrayé 3 fois l’intersection 3 à 3, qu’il faut donc re-additionner pour obtenir le bon
résultat.

1.2. Dispositions
Soit U un ensemble de cardinal |U| = n, on peut penser par exemple à l’ensemble U =
{1, 2, . . . , n} des nombres naturels inférieurs à n. Supposons de devoir choisir k éléments
parmi les n éléments de U.
On parle de disposition si on est interessés à l’ordre des éléments choisis. Nous faisons
une distinction en 2 cas différents : Dispositions sans et avec répétition.

1.2.1. Dispositions sans répétition

Nous choisissons k éléménts sans répétition (c’est-à-dire qu’on ne peut pas choisir le
même élément plusieurs fois) et en considerant l’arrangement ordonné (par exemple, les
arrangements 1 2 3 et 2 1 3 sont différents).
Le nombre de dispositions sans répétition de k éléments parmi n (k  n) est

n!
Dn,k := (n k)! = n · (n 1) · (n 2) · · · (n k + 1).

Dans la formule, la valeur n! est appélée factorielle de n ; ça corresponds au produit des

prémiers n nombres naturels, et peut être définie récursivement comme suit :

0! = 1 et n! = n · (n 1)!.

5
Explication. Nous avons n choix pour le prémier élément, mais seulement n 1 pour le
deuxième (on ne peut pas choisir le premier élément), n 2 pour le troisième, etc. pour k
fois.
Exemple 2. Nous souhaitons s’habiller différemment pendant une semaine, en évitant de
choisir la même couleur de chemise dans deux jours différents. Nous avons 10 chemises de
couleurs différentes disponibles. Il y a exactement D10,7 = 10 · 9 · 8 · 7 = 5040 dispositions
possibles. ?

Dans le language des ensembles, une disposition sans répétition de k éléments d’un en-
semble U, |U| = n, est une fonction injective d’un ensemble A de cardinal k vers U, ce
qui corresponds à choisir, ou extraire k éléments de U. La propriété d’injectivité “pour tout
a1 6= a2 dans A, f (a1 ) 6= f (a2 )” garantie la non-répétition.

1.2.2. Dispositions avec répétition

Cette fois-ci, nous pouvons choisir k éléménts avec répétition mais en considerant encore
la disposition ordonnée. Remarquons que dans ce cas k peut être superieur à n. Le nombre
de ces arrangements est

D0n,k := nk .

Explication. Nous avons n choix pour le premier éléments, même chose pour le deuxième
et pour tous les autres éléments de la suite. La suite a longueur k, donc An,k = n · n · n · · · n (k
fois) = nk .
Exemple 3 (Écriture en base 1 n avec k chiffres). Combien de nombre de au plus k chiffres
peut-on écrire en base n ? Supposons pour simplicité que n = 2 et k = 3 : nous nous intéres-
sons aux nombres qui peuvent s’écrire en base 2 (c-à-d. avec symboles 0 et 1) avec 3 chiffres
ou moins. Il y a exactement 8 = 23 = nk nombres ayant cette propriété, et précisement :

0 = 000 1 = 001 2 = 010 3 = 011

4 = 100 5 = 101 6 = 110 7 = 111

Une disposition avec répétition corresponds à une fonction (n’importe quelle) d’un en-
semble A avec k éléments à valeurs dans U. L’ensemble A contient les k places dans l’arran-
gement ordonné. Du coup on retrouve |{ f : A ! U}| = |U A | = |U||A| = nk .

1.3. Combinaisons
Dans plusieurs cas pratiques, nous sommes intéressés à des suites finis d’objets sans
spécifier un ordre, et on parle dans ce cas de combinaisons. Par exemple les arrangements
1 5 4 2 3 et 1 2 3 4 5 doivent être considerés la même combinaison des premiers cinq nombres
naturels.

1. Écrire en base n un certain nombre entier N signifie decomposer N en somme de puissances entières
successives de n : N = at nt + at 1 nt 1 + · · · + a1 n + a0 = at at 1 . . . a0 . Par exemple en base 2, on a 6 = 4 + 2 =
1 · 22 + 1 · 21 + 0 · 20 = 1 1 0. L’écriture est unique.

6
1.3.1. Combinaisons sans répétition

Si l’arrangement est non-ordonné et sans répétition, on parle de combinaison sans ré-

pétition. Le nombre de combinaisons sans répetition de k éléments parmi n éléments d’un
ensemble U (k  n) est

n n!
Cn,k = k := k!(n k)! .

Exemple 4 (Tirage sans remise). On considère une urne avec 10 boules, énumerées de 1 à 10.
On extrait k = 4 fois une boule sans remise. Si nous ne sommes pas interessés à l’ordre des
tirages, l’experience est equivalente à celle d’extraire un groupe de 4 boules au même temps.
Le nombre des possibles résultats du tirage est le nombre de combinaisons de 4 éléménts
parmi 10, c’est-à-dire C10,4 = 210. ?

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
F IGURE 1.2. Triangle de Pascal

Le nombre nk est appélé coefficient binomiale. Voici les propriétés principales des coef-
ficients binomiaux :
— n0 = nn = 1 pour tout n
— nk = n n k (symétrie)
— n+1 k = k n 1 + nk (Triangle de Pascal)
Une méthode récursive pour calculer avec les coefficients binomiaux est suggéré par la
troisième propriété decrite dessus, donné par ce qu’on appelle le Triangle de Pascal 2 (Figure
1.2).
n
Le comportement symétrique de k est montré en Figure 1.3 pour n = 20.

1.3.2. Combinaisons avec répétition

On dispose de n éléments appartenant à un ensemble U, et on souhaite un arrangement de

taille k non-ordonné et avec répétition, ce qu’on appelle une combinaison avec répétition.
Le nombre de ces combinaisons est
0 =C
Cn,k n+k 1,k .

Explication. Toute combinaison de k éléments avec répétition à choisir parmi n éléments

a1 , . . . , an donnés peut s’écrire (sans perte de généralité) comme suit :
a1 . . . a1 , a2 . . . a2 , . . . , an . . . an
| {z } | {z } | {z }
k1 fois k2 fois kn fois

2. Le niveau est donné par n, alors que la profondité dans chaque niveau est donnée par k : n+1
k est donné
par la somme des coefficients binomiaux à niveau n et profondité k et k 1 (en Figure 1.2, le 10 est la somme
de 6 et 4).

7
 ·105
2.0

1.5

1.0

0.5

0.0

0 5 10 15 20
20
F IGURE 1.3. Valeurs du coefficient binomiale k , pour k = 0, . . . , 20.

avec k1 + · · · + kn = k. Cela correspond à placer k objets dans n boîtes, et, après, à appeler ai
tous les objets placé dans la i ème boîte. De manière équivalente, à placer n 1 “cloisons”
séparants k objets :

a1 . . . a1 q1 a2 . . . a2 q2 . . . qn 1 an . . . an .
| {z } |{z} | {z } |{z} |{z} | {z }
k1 fois cloison k2 fois cloison cloison kn fois

Du coup le nombre de combinaisons avec répétition des éléments a1 , . . . , an pris k à k est

le nombre de combinaisons de n 1 objets parmi k + n 1, c’est-à-dire Cn+k 1,n 1 (=
Cn+k 1,k ).
Exemple 5 (Nombre de monômes de degré k). Soit x = (x1 , . . . , xn ) un vecteur de n variables,
et soit k 2 . Le nombre de monômes de degré k en x est donné par le nombre de combi-
naisons avec répétition pris k à k, des éléments de U = {x1 , . . . , xn } (combinaisons car le
produit de variables étant commutatif, on ne s’interesse pas à l’ordre ; avec répétition car
une variable peut apparaître avec puissance 2). ?
0 = C0
La propriété Cn,k 0
n,k 1 + Cn 1,k est une consequence directe du Triangle de Pascal
appliqué à Cn+k 1,k : Cn+k 1,k = Cn+k 2,k 1 +Cn+k 2,k .

1.4. Permutations
Nous donnons un nom special aux arrangements de n éléments parmi n (k = n en Section
1.2) : permutation. La possibilité de répétition joue un rôle aussi pour les permutations.

1.4.1. Permutations sans répétition

Il s’agit d’une disposition sans répétition de n éléments parmi n. Donc le nombre total de
ces arrangements est :

Pn := Dn,n = n!

Exemple 6 (Code confidentiel). Le code confidentiel d’une certaine carte de crédit est fait
par les nombres 1, 2, 6, 9. Combien de tentatif faut-il faire pour être sûrs de saisir le code
correct (code de 4 chiffres) ? Exactement P4 = 4! = 24 tentatifs. ?

8
1.4.2. Permutations avec répétition

Nous considerons un ensemble U de n éléments, et des nombres naturels k1 , . . . , kn . Nous

souhaitons obtenir un arrangement de k1 + · · · + kn éléments ou n sont distincts (les éléments
de U) et où les elements de U se répètent respectivement k1 , . . . , kn fois.
Exemple 7 (Nombre d’anagrammes). Un anagramme d’un mot donné est une autre mot (pas
forcement listé dans le vocabulaire) qui utilise les mêmes lettres. Par exemple, PARISIEN est
un anagramme (avec sens) de ASPIRINE : dans ce cas U = {A, S, P, I, R, N, E}, n = |U| = 7,
k1 + · · · + k7 = 8 = longueur du mot. La lettre I apparait 2 fois, du coup il faut diviser par
2! = 2 le nombre total de permutations de Section 1.4.1, donc le nombre d’anagrammes est
= 8!/2! = 20160. ?

En généralisant l’example précedent, on voit que le nombre de permutations de k élé-

ments où n sont distincts (ou permutations avec répétitions k1 , . . . , kn ) est

(k1 +···+kn )!
0
Pn,k1 ,...,kn
:= Ck1 +···+kn ,k1 ·Ck2 +···+kn ,k2 · · · Ckn ,kn = k1 !k2 !···kn ! .

Explication. Pour construire une suite de k1 + · · · + kn éléments avec les répétitions donnée,
nous devons choisir (combinaisons, car l’ordre n’intervient pas)
— les k1 emplacements du premier élément de U, parmi k1 + · · · + kn places
— les k2 emplacements du deuxième élément de U, parmi k2 + · · · + kn places
— ...
— les kn emplacements du dernier élément de U, parmi kn places
ce qui donne les produit des coefficients Cki +···+kn ,ki , pour i = 1, . . . , n. La deuxième egalité
suit simplement en utilisant la définition de Cki +···+kn ,ki :
(
( ⇠
(k1 + · · · + kn )! ( (k( (·(
2+ · ·(+( kn )! (k⇠ ⇠⇠
1 + kn )! (kn )!
n ⇠ (k1 + · · · + kn )!
( ( · · · ⇠ =
( ( ( ( ( (
k1 !(
(k(
2+(·( · · + kn )! k2 !(
(k(
3+(·( · · + kn )! kn 1 !(kn )! kn ! k1 ! · · · kn !

Tableau récapitulatif :

Arrangement Répétition Nombre Exemple

Dispositions sans Dn,k = (n n!k)! Ex. 2 : Façons de s’habiller.
Dispositions avec D0n,k = nk Ex. 3 : Écriture en base n.
Combinaisons sans Cn,k = nk Ex. 4 : Tirages sans remise.
Combinaisons avec 0 = n+k 1 .
Cn,k Ex. 5 : Nombre de monômes.
k
Permutations sans Pn = n! Ex. 6 : Code confidentiel.
Permutations avec 0
Pn,k1 ,...,kn
= (kk11 !k
+···+kn )!
2 !···kn !
Ex. 7 : Anagrammes.

1.5. Théorème du binôme

Les coefficients binomiaux apparaissent en un résultat de base de combinatoire.

Théorème 8 (Théorème du binôme). Pour tout a, b 2 et n 2

✓ ◆n
n k n k
(a + b) = Â
n
ab .
k=0 k

9
Démonstration. Soit Pn la propriété à prouver pour n 2 . La preuve est par récurrence 3
sur n. Pour n = 0, la propriété est verifiée puisque
✓ ◆
0 0 0 0
(a + b) = 1 et a b = 1.
0

Supposons Pn vraie. On a que

✓ ◆ n
n k n
(a + b) = (a + b)(a + b) = (a + b) Â
n+1 n
ab k
=
k=0 k
n ✓ ◆ n ✓ ◆
n k+1 n k n k n k+1 p=k+1
=Â a b +Â ab =
k=0 k k=0 k
⇣ ⌘
n p+1 + n n n
= Ânp=1 p 1 a p bn n an+1 b0 + 0 a0 bn+1 + Ânk=1 k ak bn k+1 =
n ✓✓
✓ ◆◆ ◆
n n p+1 Pascal
=a n+1
+b n+1
+Â + a p bn =
p=1 p 1 p
n ✓ ◆
n + 1 p n p+1
=a n+1
+b n+1
+Â a b =
p=1 p
n+1 ✓ ◆
n + 1 p n p+1
= Â a b
p=0 p

ce qui montre que Pn+1 est vraie. ⌅

Exemples de développements du binôme (a + b)n à comparer avec le Triangle de Pascal

de page 7 :

(a + b)3 = a3 + 3a2 b + 3ab2 + b3

(a + b)4 = a4 + 4a3 b + 6a2 b2 + 4ab3 + b4
(a + b)5 = a5 + 5a4 b + 10a3 b2 + 10a2 b3 + 5ab4 + b5
(a + b)6 = a6 + 6a5 b + 15a4 b2 + 20a3 b3 + 15a2 b4 + 6ab5 + b6

3. Soit Pn une propriété parametrisée par n 2 . Une preuve de Pn par recurrence sur n est donnée par : (1)
une preuve de P0 et (2) une preuve de l’implication Pn ! Pn+1 .

10