Combinatoire & dénombrement

Les prérequis en 30 secondes

Deux choses à avoir en tête et tu es prêt.

La factorielle $n!$ (« factorielle $n$ ») est le produit de tous les entiers de $1$ à $n$ :

$n! = n \times (n-1) \times \cdots \times 2 \times 1$.

Par exemple $3! = 3 \times 2 \times 1 = 6$ et $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. Convention à connaître : $0! = 1$.

Le principe multiplicatif : si un choix se fait en plusieurs étapes indépendantes, on multiplie le nombre de possibilités de chaque étape. Deux entrées puis trois plats, ça fait $2 \times 3 = 6$ menus.

L'essentiel : une seule question à te poser

Devant un exercice de dénombrement, pose-toi toujours la même question : est-ce que l'ordre compte ?

L'ordre compte (comme un podium or / argent / bronze) : tu utilises un arrangement, $\dfrac{n!}{(n-k)!}$.

L'ordre ne compte pas (comme choisir une équipe) : tu utilises une combinaison, $\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$, qu'on lit « $k$ parmi $n$ ».

Tu ranges tous les éléments ? C'est une permutation : $n!$.

À retenir aussi : $\dbinom{n}{0} = \dbinom{n}{n} = 1$ et $\dbinom{n}{1} = n$. Sur ta calculatrice, $\dbinom{n}{k}$ se tape souvent avec la touche $\text{nCr}$.

Un exemple traité en entier

Énoncé. On forme un comité de $3$ personnes choisies parmi $10$. Combien de comités différents possibles ?

Étape 1 — l'ordre compte-t-il ? Un comité, c'est juste un groupe : le comité { Alice, Bob, Chloé } est le même que { Chloé, Alice, Bob }. L'ordre ne compte pas, et personne n'est choisi deux fois : c'est une combinaison.

Étape 2 — j'écris la formule. Nombre de comités $= \dbinom{10}{3} = \dfrac{10!}{3!\,7!}$.

Étape 3 — je simplifie. $\dbinom{10}{3} = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1}$.

Étape 4 — je calcule. $\dfrac{720}{6} = 120$.

Réponse. Il y a $\mathbf{120}$ comités possibles.

Le principe multiplicatif, socle de tout

Dénombrer, c'est compter le nombre de façons de réaliser un choix, sans tout écrire. La méthode générale : découper le choix en étapes.

Principe multiplicatif. Si un choix se fait en $p$ étapes indépendantes offrant respectivement $n_1, n_2, \dots, n_p$ possibilités, le nombre total de résultats est

$n_1 \times n_2 \times \cdots \times n_p$.

Exemple. Un menu = une entrée parmi $2$, puis un plat parmi $3$. Chaque entrée peut être suivie de n'importe quel plat, donc on multiplie : $2 \times 3 = 6$ menus. L'arbre ci-contre le montre : $2$ branches, puis $3$ branches sur chacune, soit $6$ feuilles.

Les trois outils : permutations, arrangements, combinaisons

Permutation. Ranger tous les $n$ éléments dans un ordre : il y a $n!$ façons.
Exemple : ranger $3$ livres distincts sur une étagère $\rightarrow 3! = 6$ rangements.

Arrangement (ou $k$-liste sans répétition). Choisir $k$ éléments parmi $n$ en tenant compte de l'ordre, sans répétition :

$\dfrac{n!}{(n-k)!} = n \times (n-1) \times \cdots \times (n-k+1)$.
Exemple : mots de $2$ lettres distinctes avec $\{A, B, C\}$ $\rightarrow \dfrac{3!}{1!} = 3 \times 2 = 6$ (AB, BA, AC, CA, BC, CB).

Combinaison. Choisir $k$ éléments parmi $n$ sans tenir compte de l'ordre :

$\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$.
Exemple : nombre de poignées de main entre $4$ personnes (une poignée = une paire, l'ordre est sans importance) $\rightarrow \dbinom{4}{2} = \dfrac{4 \times 3}{2 \times 1} = 6$.

Le lien entre les deux : un arrangement, c'est une combinaison que l'on ordonne ensuite, d'où $\dfrac{n!}{(n-k)!} = \dbinom{n}{k} \times k!$.

Les coefficients binomiaux

Le nombre $\dbinom{n}{k}$, lu « $k$ parmi $n$ », est le nombre de parties à $k$ éléments d'un ensemble à $n$ éléments (l'ordre ne compte pas). C'est un coefficient binomial.

Conventions. Comme $0! = 1$ : $\dbinom{n}{0} = 1$ (une seule partie vide), $\dbinom{n}{n} = 1$ (l'ensemble entier), et $\dbinom{n}{1} = n$.

Symétrie. $\dbinom{n}{k} = \dbinom{n}{n-k}$ : choisir les $k$ que l'on garde revient à choisir les $n-k$ que l'on laisse.

Relation de Pascal. $\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$. Elle permet de calculer les coefficients de proche en proche.

Lien avec la loi binomiale (revu en probabilités) : si $X$ suit la loi binomiale de paramètres $n$ et $p$, alors $P(X = k) = \dbinom{n}{k}\,p^{k}\,(1-p)^{n-k}$. Le coefficient binomial y compte les positions possibles des $k$ succès.

Exemple 1 — un podium (l'ordre compte)

Énoncé. $8$ coureurs participent à une course. Combien de podiums (or, argent, bronze) différents peut-on avoir ?

On réfléchit ensemble. Ici l'or, l'argent et le bronze sont des places distinctes : le podium (A, B, C) n'est pas le même que (B, A, C). Donc l'ordre compte, et un coureur ne peut pas prendre deux médailles : pas de répétition. C'est un arrangement de $3$ parmi $8$.

On pose la formule. Nombre de podiums $= \dfrac{8!}{(8-3)!} = \dfrac{8!}{5!}$.

On simplifie. $\dfrac{8!}{5!} = 8 \times 7 \times 6$ (les facteurs de $1$ à $5$ se simplifient).

On calcule. $8 \times 7 \times 6 = 336$.

Réponse. Il y a $\mathbf{336}$ podiums possibles.

Exemple 2 — une main de cartes (l'ordre ne compte pas)

Énoncé. On tire simultanément $5$ cartes d'un jeu de $32$. Combien de mains différentes ?

On réfléchit ensemble. Une main, c'est un paquet de $5$ cartes : l'ordre dans lequel on les a tirées ne change rien. « Tirage simultané » est le mot-clé qui signale l'ordre ne compte pas : c'est une combinaison de $5$ parmi $32$.

On pose la formule. Nombre de mains $= \dbinom{32}{5} = \dfrac{32!}{5!\,27!}$.

On simplifie. $\dbinom{32}{5} = \dfrac{32 \times 31 \times 30 \times 29 \times 28}{5 \times 4 \times 3 \times 2 \times 1}$.

On calcule le haut et le bas. Numérateur $= 24\,165\,120$ ; dénominateur $= 120$.

On divise. $\dfrac{24\,165\,120}{120} = 201\,376$.

Réponse. Il y a $\mathbf{201\,376}$ mains possibles.

Exemple 3 — plusieurs étapes (on multiplie)

Énoncé. Un cadenas a un code de $3$ chiffres, chaque chiffre allant de $0$ à $9$, et les répétitions sont autorisées. Combien de codes possibles ?

On réfléchit ensemble. Trois étapes : choisir le 1er chiffre, puis le 2e, puis le 3e. Chaque étape a $10$ possibilités ($0$ à $9$), et comme les répétitions sont permises, le choix d'une étape n'enlève rien aux suivantes : étapes indépendantes. On applique le principe multiplicatif.

On pose le produit. Nombre de codes $= 10 \times 10 \times 10$.

On calcule. $10 \times 10 \times 10 = 10^{3} = 1000$.

Réponse. Il y a $\mathbf{1000}$ codes possibles (de $000$ à $999$).

Le piège à voir. Si les chiffres devaient être tous différents, l'ordre compterait toujours mais sans répétition : ce serait un arrangement $\dfrac{10!}{7!} = 10 \times 9 \times 8 = 720$.

Les subtilités et ce que le correcteur attend

Justifie ton choix d'outil. Un résultat juste sans justification perd des points. Écris toujours une phrase du type « l'ordre ne compte pas, c'est une combinaison » avant de poser la formule.

Repère les mots-clés. « tirage successif » ou « l'un après l'autre » → l'ordre compte (arrangement). « tirage simultané » ou « en même temps » → l'ordre ne compte pas (combinaison).

Pièges classiques à éviter.

• Confondre arrangement (ordre) et combinaison (sans ordre) : c'est l'erreur numéro un.
• Oublier les valeurs simples : $\dbinom{n}{0} = 1$ et $\dbinom{n}{1} = n$.
• Quand un choix se fait en deux groupes (ex. hommes ET femmes), il faut multiplier les deux combinaisons, pas les additionner.
• « au moins un » : passe souvent par l'événement contraire (total moins les cas « aucun »).

Soigne la rédaction du calcul. Pose $\dbinom{n}{k}$, remplace par la fraction, simplifie, donne la valeur finale. Le correcteur note les étapes, pas seulement le résultat.

Problème type 1 — un comité mixte

Énoncé. Une classe compte $7$ garçons et $5$ filles. On forme un comité de $4$ élèves comprenant exactement $2$ garçons et $2$ filles. Combien de comités possibles ?

Étape 1 — je découpe en deux choix indépendants. Choisir les garçons, puis choisir les filles. Dans un comité l'ordre ne compte pas : deux combinaisons.

Étape 2 — les garçons. $2$ garçons parmi $7$ : $\dbinom{7}{2} = \dfrac{7 \times 6}{2 \times 1} = 21$.

Étape 3 — les filles. $2$ filles parmi $5$ : $\dbinom{5}{2} = \dfrac{5 \times 4}{2 \times 1} = 10$.

Étape 4 — je combine. Chaque choix de garçons peut s'associer à chaque choix de filles : principe multiplicatif, donc $\dbinom{7}{2} \times \dbinom{5}{2} = 21 \times 10$.

Résultat. $21 \times 10 = 210$ comités possibles.

Ce que le correcteur attend : avoir vu qu'il faut multiplier les deux combinaisons (piège fréquent : additionner ou n'en calculer qu'une).

Problème type 2 — vers la loi binomiale

Énoncé. On lance $10$ fois une pièce équilibrée. Quelle est la probabilité d'obtenir exactement $4$ fois « pile » ?

Étape 1 — je reconnais la situation. $10$ lancers indépendants, deux issues à chaque fois, même probabilité $p = \tfrac{1}{2}$ : le nombre de « pile » suit une loi binomiale de paramètres $n = 10$ et $p = \tfrac{1}{2}$.

Étape 2 — j'écris la formule. $P(X = 4) = \dbinom{10}{4}\,\left(\tfrac{1}{2}\right)^{4}\left(\tfrac{1}{2}\right)^{6}$.

Étape 3 — pourquoi le coefficient binomial. $\dbinom{10}{4}$ compte les façons de placer les $4$ « pile » parmi les $10$ lancers : $\dbinom{10}{4} = \dfrac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 210$.

Étape 4 — je regroupe les puissances. $\left(\tfrac{1}{2}\right)^{4}\left(\tfrac{1}{2}\right)^{6} = \left(\tfrac{1}{2}\right)^{10} = \dfrac{1}{1024}$.

Étape 5 — je conclus. $P(X = 4) = \dfrac{210}{1024} \approx 0{,}205$, soit environ $20{,}5\,\%$.

La leçon : le dénombrement (le $\dbinom{n}{k}$) est le cœur de la loi binomiale — d'où l'intérêt de bien le maîtriser.

Le triangle de Pascal

La relation de Pascal $\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$ permet de construire tous les coefficients binomiaux sans jamais calculer de factorielle, en les empilant en triangle.

On commence chaque ligne et on la finit par un $1$ (car $\dbinom{n}{0} = \dbinom{n}{n} = 1$), et chaque terme intérieur est la somme des deux termes juste au-dessus de lui.

Sur la figure, la ligne $n = 4$ donne $1,\ 4,\ 6,\ 4,\ 1$ : ce sont exactement $\dbinom{4}{0}, \dbinom{4}{1}, \dbinom{4}{2}, \dbinom{4}{3}, \dbinom{4}{4}$. Et le $6$ du milieu vient bien de $3 + 3$, deux coefficients de la ligne du dessus.

On y voit aussi la symétrie $\dbinom{n}{k} = \dbinom{n}{n-k}$ : chaque ligne se lit pareil de gauche à droite et de droite à gauche.

La formule du binôme de Newton

Les coefficients binomiaux portent ce nom parce qu'ils apparaissent quand on développe une puissance de somme. C'est la formule du binôme de Newton :

$(a + b)^{n} = \displaystyle\sum_{k=0}^{n} \dbinom{n}{k}\,a^{k}\,b^{n-k}$.

Exemple avec $n = 4$. On lit les coefficients sur la ligne $4$ du triangle de Pascal ($1, 4, 6, 4, 1$) :

$(a + b)^{4} = a^{4} + 4a^{3}b + 6a^{2}b^{2} + 4ab^{3} + b^{4}$.

Pourquoi le coefficient binomial ? En développant $(a+b)^4 = (a+b)(a+b)(a+b)(a+b)$, un terme $a^{2}b^{2}$ s'obtient en choisissant dans quels $2$ facteurs (sur $4$) on prend le $a$ : il y a $\dbinom{4}{2} = 6$ façons, d'où le $6$.

Un cas amusant : avec $a = b = 1$, la formule donne $\displaystyle\sum_{k=0}^{n} \dbinom{n}{k} = 2^{n}$ — la somme d'une ligne du triangle de Pascal est une puissance de $2$.

Pourquoi ça marche, et l'an prochain

Démontrer la symétrie sans calcul. $\dbinom{n}{k} = \dbinom{n}{n-k}$ se prouve par un argument de dénombrement : choisir les $k$ éléments que l'on garde, c'est la même chose que choisir les $n-k$ éléments que l'on écarte. À chaque partie de $k$ correspond exactement une partie de $n-k$ : les deux nombres sont donc égaux. Ce type de preuve « par correspondance » (bijection) est une idée que tu retrouveras beaucoup.

Démontrer Pascal, même esprit. Pour compter les parties à $k$ éléments parmi $n$, fixe un élément particulier $x$. Soit une partie contient $x$ (il reste $k-1$ éléments à choisir parmi les $n-1$ autres : $\dbinom{n-1}{k-1}$), soit elle ne le contient pas ($k$ éléments parmi $n-1$ : $\dbinom{n-1}{k}$). En additionnant ces deux cas disjoints, on retrouve $\dbinom{n}{k}$.

Là où ça mène. En probabilités, le dénombrement alimente directement la loi binomiale $P(X=k) = \dbinom{n}{k}p^{k}(1-p)^{n-k}$, puis l'étude de son espérance, de sa concentration et de l'estimation. En études supérieures, tu croiseras d'autres modèles de comptage (avec ordre et répétition, tirages avec remise) et le dénombrement devient un outil de base en informatique, en probabilités et en algèbre.