L'analyse combinatoire

🎯 Objectifs du chapitre — À la fin de ce chapitre, vous saurez :

• utiliser les principes additif et multiplicatif pour compter des possibilités ;
• distinguer p-listes, arrangements, permutations et combinaisons ;
• dénombrer des permutations avec répétition (anagrammes, répartitions en groupes) ;
• utiliser les propriétés des coefficients binomiaux, le triangle de Pascal et la formule du binôme ;
• traduire un tirage (simultané, successif avec ou sans remise) en formule de dénombrement.

1.1 Pourquoi dénombrer ?

Dans de très nombreuses situations, tous les résultats d'une expérience ont la même chance de se produire : tirer une carte au hasard, choisir un client dans un fichier, désigner une commission par tirage au sort. La probabilité d'un événement se calcule alors comme le rapport du nombre de cas favorables au nombre de cas possibles. Encore faut-il savoir compter ces cas sans les écrire un par un : c'est l'objet de l'analyse combinatoire, première brique du cours de probabilités.

Définition — Cardinal : le cardinal d'un ensemble fini $E$, noté $\text{card}(E)$ ou $|E|$, est le nombre de ses éléments.

Deux règles fondent tous les calculs :

• Principe additif : si un choix se fait soit dans $E$, soit dans $F$, avec $E$ et $F$ disjoints, il y a $|E| + |F|$ possibilités. Plus généralement, $|E \cup F| = |E| + |F| - |E \cap F|$.
• Principe multiplicatif : si un choix se fait en plusieurs étapes successives, avec $n_1$ possibilités pour la première, $n_2$ pour la deuxième, etc., il y a $n_1 \times n_2 \times \dots \times n_k$ possibilités au total. C'est le cardinal d'un produit cartésien.

Exemple : un restaurant de Fès propose 4 entrées, 5 plats et 3 desserts. Un menu complet se compose de $4 \times 5 \times 3 = 60$ façons. Si le client prend soit une entrée, soit un dessert (et un plat), il a $(4 + 3) \times 5 = 35$ choix.

1.2 Les p-listes : ordre et répétition

Définition — p-liste : suite ordonnée de $p$ éléments d'un ensemble à $n$ éléments, avec répétition possible.

Chaque position peut accueillir n'importe lequel des $n$ éléments, d'où, par le principe multiplicatif :

$$\boxed{\text{nombre de p-listes} = n^p}$$

Un code PIN à 4 chiffres : $10^4 = 10\,000$ codes. Un questionnaire de 10 questions par « oui » ou « non » : $2^{10} = 1\,024$ grilles de réponses. Un identifiant de 3 lettres suivies de 3 chiffres : $26^3 \times 10^3 = 17\,576\,000$ identifiants.

1.3 Les arrangements et les permutations

Définition — Arrangement : suite ordonnée de $p$ éléments distincts choisis parmi $n$ ($p \le n$).

Le premier élément se choisit de $n$ façons, le deuxième de $n - 1$ (on ne peut pas reprendre le premier), et ainsi de suite jusqu'au $p$-ième :

$$\boxed{A_n^p = n\,(n - 1)\cdots(n - p + 1) = \frac{n!}{(n - p)!}}$$

où $n! = n \times (n - 1) \times \dots \times 2 \times 1$ se lit « factorielle $n$ », avec la convention $0! = 1$.

Lorsque $p = n$, on range tous les éléments : c'est une permutation, et il y en a $A_n^n = n!$. Ranger 6 dossiers sur une étagère : $6! = 720$ ordres possibles.

Exemple : 12 candidats se présentent au bureau d'une association d'étudiants de Rabat, qui compte un président, un vice-président et un trésorier. Le nombre de bureaux possibles est $A_{12}^3 = 12 \times 11 \times 10 = 1\,320$ : l'ordre compte, car les fonctions sont différentes.

Permutations avec répétition. Si parmi $n$ objets, $n_1$ sont identiques entre eux, $n_2$ identiques entre eux, etc. (avec $n_1 + \dots + n_k = n$), le nombre de rangements distincts est :

$$\frac{n!}{n_1!\,n_2!\cdots n_k!}$$

Les anagrammes du mot AGADIR (deux A) : $6!/2! = 360$. Répartir 10 stagiaires en trois groupes de 5, 3 et 2 affectés à trois services différents : $10!/(5!\,3!\,2!) = 2\,520$ façons.

1.4 Les combinaisons

Définition — Combinaison : partie (sous-ensemble) de $p$ éléments distincts choisis parmi $n$, sans tenir compte de l'ordre.

Chaque combinaison de $p$ éléments peut être ordonnée de $p!$ façons et donne ainsi $p!$ arrangements. Donc :

$$\boxed{C_n^p = \binom{n}{p} = \frac{A_n^p}{p!} = \frac{n!}{p!\,(n - p)!}}$$

Former une commission de 3 membres parmi 12, sans fonction distincte : $C_{12}^3 = 1\,320 / 6 = 220$ commissions. On retrouve le lien entre les deux notions : 220 commissions × 6 façons de répartir les trois fonctions = 1 320 bureaux.

Propriétés à connaître :

Propriété	Formule	Idée
Valeurs simples	$C_n^0 = C_n^n = 1$ ; $C_n^1 = n$	Une seule façon de ne rien prendre ou de tout prendre
Symétrie	$C_n^p = C_n^{n - p}$	Choisir les $p$ retenus revient à choisir les $n - p$ exclus
Relation de Pascal	$C_n^p = C_{n-1}^{p-1} + C_{n-1}^p$	Un élément donné est pris ou non
Somme	$\sum_{p=0}^{n} C_n^p = 2^n$	Nombre total de sous-ensembles d'un ensemble à $n$ éléments

La relation de Pascal permet de construire le triangle de Pascal, où chaque nombre est la somme des deux nombres situés au-dessus de lui :

$n$	Coefficients $C_n^0, C_n^1, \dots, C_n^n$
0	1
1	1 1
2	1 2 1
3	1 3 3 1
4	1 4 6 4 1
5	1 5 10 10 5 1

1.5 La formule du binôme de Newton

$$\boxed{(a + b)^n = \sum_{k=0}^{n} C_n^k\,a^k\,b^{n-k}}$$

Les coefficients binomiaux $C_n^k$ doivent leur nom à cette formule. Par exemple $(a + b)^4 = a^4 + 4a^3 b + 6a^2 b^2 + 4a b^3 + b^4$. Cette formule reviendra dans la loi binomiale : la somme des probabilités $C_n^k\,p^k\,(1 - p)^{n-k}$ vaut $(p + 1 - p)^n = 1$.

1.6 Les combinaisons avec répétition

Il arrive que l'on choisisse $p$ objets parmi $n$ types, sans ordre, en pouvant prendre plusieurs fois le même type : composer un panier de 5 fruits parmi 3 variétés, répartir des bons d'achat identiques entre plusieurs magasins. Le nombre de possibilités est :

$$C_{n + p - 1}^p$$

Répartir 5 bons d'achat identiques entre 3 magasins : $C_7^5 = C_7^2 = 21$ façons. Cette formule est moins fréquente à l'examen, mais elle évite une erreur classique : utiliser $n^p$ alors que les objets sont indiscernables.

1.7 Modéliser un tirage

La difficulté n'est presque jamais la formule, mais le choix de la formule. Tout repose sur deux questions : l'ordre compte-t-il ? un même élément peut-il être choisi plusieurs fois ?

Type de tirage de $p$ éléments parmi $n$	Ordre	Répétition	Nombre de résultats
Successif avec remise	Oui	Oui	$n^p$
Successif sans remise	Oui	Non	$A_n^p$
Simultané (poignée)	Non	Non	$C_n^p$

Lorsque l'énoncé impose une composition (« exactement 2 femmes et 1 homme »), on multiplie les choix faits dans chaque sous-groupe : $C_{n_1}^{k_1} \times C_{n_2}^{k_2}$. Lorsqu'il demande « au moins un », on compte plus facilement le complémentaire (« aucun ») et on le retranche du total.

1.8 Méthode : résoudre un exercice de dénombrement

1. Décrire précisément un résultat : une liste ordonnée, un ensemble, un rangement ?
2. Répondre aux deux questions : ordre ? répétition ? En déduire la formule ($n^p$, $A_n^p$, $C_n^p$, $n!$).
3. Découper le choix en étapes (principe multiplicatif) ou en cas disjoints (principe additif).
4. Pour « au moins », passer par le complémentaire.
5. Contrôler l'ordre de grandeur, et vérifier sur un petit cas si le doute persiste.

⚠️ Les pièges à éviter

• Utiliser un arrangement pour une commission sans fonction : l'ordre ne compte pas, c'est une combinaison.
• Additionner au lieu de multiplier quand le choix se fait en étapes successives (et inversement pour des cas disjoints).
• Compter « au moins un » directement en additionnant des cas qui se recouvrent.
• Oublier de diviser par $n_1!\,n_2!\cdots$ quand certains objets sont identiques.
• Oublier que $0! = 1$, ce qui fausse $C_n^0$ ou $C_n^n$.