Analyse combinatoire

L’analyse combinatoire est une branche des mathématiques qui étudie comment compter de façons de ranger des
objets. Elle fournit des méthodes de dénombrements utiles qu’on utilise dans le calcul des probabilités.

1. Principe fondamental de l’analyse combinatoire

Soit une expérience aléatoire E composée de r expériences successives, la première pouvant produire un résultat
quelconque parmi n1 résultats possibles, la deuxième produisant un résultat quelconque parmi n2 résultats possibles,
· · · , la r ime pouvant produire un résultat quelconque parmi n r résultats possibles. Le nombre total de résultats possibles
pour l’expérience aléatoire E est le produit de
n1 × n2 × n3 × · · · × n r

Exemple 1.
Les localités A et B sont reliées par n1 = 3 routes différentes et les localités B et C par n2 = 2 routes différentes ;
alors il y a N = 3 × 2 = 6 manières différentes de se rendre par la route de la localité A à la localité C.

2. Arrangements
Envisageons un ensemble de n objets différents. Choisissons maintenant r de ces n objets et ordonnons les (on a
obligatoirement r 6 n).

2.1. Arrangement sans répétition

Définition 1.1

On appelle arrangement sans répétition de r éléments pris parmi les n éléments de E, toute disposition
ordonnée de r éléments différents de E.

Proposition 1.1

Soit,
n!
Arn = n(n − 1)(n − 2) · · · (n − r + 1) = ,
(n − r)!
est le nombre d’arrangements sans répétition de r éléments pris dans un ensemble E à n éléments.

rappel n! (lire “factorielle n”) est le produit de tous les entiers jusqu’à n, n! = n(n − 1)(n − 2) · · · 3.2.1. Par convention,
0! = 1.
Exemple 2.
4!
Les arrangements de deux lettres prises parmi 4 lettres {a, b, c, d} sont au nombre de A24 = 2! = 12. Ce sont :
(a, b), (a, c), (a, d), (b, a), (b, c), (b, d), (c, a), (c, b), (c, d), (d, a), (d, b), (d, c).

Cas particulier : r = n Il s’agit d’ordonner n objets entre eux, c’est-à-dire d’effectuer une permutation de ces n objets.
ANALYSE COMBINATOIRE 4. PERMUTATIONS SANS RÉPÉTITION 2

2.2. Arrangement avec répétition

Définition 1.2

On appelle arrangement avec répétition de r éléments pris parmi les n éléments de E, toute disposition
ordonnée de r éléments non nécessairement différents de E.

Proposition 1.2

Soit,
Arn = n r ,
le nombre d’arrangement avec répétition de r éléments pris parmi les n éléments de E.

Exemple 3.
Dans une urne contenant n boules numérotées, on tire r boules l’une après l’autre (on s’intéresse à l’ordre ) en
les remettant dans l’urne après chaque tirage (on accepte les répétitions), le nombre de tirages possibles est le
nombre d’arrangement avec répétition de r éléments pris parmi les 1, 2, 3, · · · , n c’est-à-dire n r .

3. Permutations

4. Permutations sans répétition

Définition 1.3

Une permutation de n éléments est une disposition ordonnée de ces n éléments.

Proposition 1.3

Les permutations de n éléments sans répétition est donné par

Pn = Ann = n!.

Exemple 4.
On souhaite ranger sur une étagère 10 livres distincts. Combien de façons possible peut-on les ranger. Le nombre
de permutations à 10 livres est 10!

4.1. Permutation avec répétition

Si les n objets de E sont partitionnés en k, groupes G1 ,G2 , · · · , Gk de cardinaux respectifs n1 ,n2 , · · · , nk , et que à
l’intérieure de chaque groupe les objets sont identiques.
Définition 1.4

On appelle permutation avec répétition de n éléments de E ; répartit en k catégories ; qui est rapporté aux
nombre de permutations de chaque catégories.

Proposition 1.4

Soit,
n!
P̃n =
n1 ! × n2 ! × n3 ! × · · · × nk !
le nombre de permutations avec répétition des n éléments de l’ensemble E (répartie en k catégories).
ANALYSE COMBINATOIRE 5. COMBINAISONS 3

Exemple 5.
Le nombre de tirages distincts possible qu’on peut faire à partir de 5 boules, reparties en 2 boules blanches et 3
5!
noires est P̃5 = = 10.
2! × 3!

5. Combinaisons

Définition 1.5

Soit E un ensemble de n objets, on appelle combinaison de r objets parmi n tout ensemble de r objets parmi
les n objets de E.

Remarque 1.1

On parle alors d’ensemble et non pas de suite car, pour les combinaisons, la notion d’ordre des objets n’est pas
prise en considération.

5.1. Combinaisons sans répétition

Définition 1.6

On appelle combinaison sans répétition de r éléments pris parmi les n éléments d’un ensemble E toute
disposition non ordonnée de r éléments de E.

Exemple 6.
Les combinaisons sans répétition de 2 éléments de 1, 2, 3 sont
(1, 2), (1, 3), (2, 3).

Proposition 1.5

Le nombre de combinaison de r objets pris parmi n sans remise est donné par :
Arn n!
Cnr = =
r! r!(n − r)!
 
r
Il est noté aussi
n

Exemple 7.
Un enseignant désire confectionner un QCM qui comporte 10 questions. Pour ce faire, il choisit au hasard 40
questions différentes ayant déjà été traité en cours. Combien de sujets différent peut-il préparer ?
10
Il y a C40 façon de choisir un QCM de 10 questions parmi 40 questions,
10 40!
C40 = = 847660528
10!(40 − 10)!

Remarque 1.2

• Cnr = 0 si r > n,
• Cnr = Cnn−r et en particulier Cn0 = Cnn = 1 de plus Cn1 = Cnn−1 = n,
• L’inégalité
r
Cn+1 = Cnr + Cnr−1
est appelée Formule du triangle de Pascal.
ANALYSE COMBINATOIRE 5. COMBINAISONS 4

• L’identité
n
X
(a + b)n = Cni a i b n−i
i=0
est appelée Formule du Binôme de Newton. Cas particulier,
Xn
2n = Cni .
i=0

Exemple 8.

2
X
(a + b)2 = C2i a i b2−i = C20 a0 b2−0 + C21 a1 b2−1 + C22 a2 b2−2 = b2 + 2ab + a2 .
i=0

5.2. Combinaison avec répétition

Définition 1.7

On appelle combinaison avec répétition de r éléments pris parmi les n éléments d’un ensemble E toute
disposition non ordonnée de r éléments, non nécessairement différents de E.

Exemple 9.
Les combinaisons avec répétition de 2 éléments de 1, 2, 3 sont
(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)

Proposition 1.6

Le nombre de combinaison de r objets pris parmi n avec remise est donné par :
r
Cn+r−1

Exemple 10.
Dans une urne contenant 10 boules distinguables (numérotées), on tire 3 boules en les remettant dans l’urne après
chaque tirage (on accepte les répétitions). On ne s’intéresse pas à l’ordre d’apparition des boules. Le nombre de
tirages possible est le nombre de combinaisons avec répétition à 3 éléments de l’ensemble 1, 2, 3, 4, 5, 6, 8, 9, 10
3
c-à-d. C10+3−1 = 220.