Imaginez qu’un verrou à code à 4 chiffres distincts vous soit imposé. Combien de codes différents peut-on former ? La réponse « 5 040 » illustre parfaitement la puissance du dénombrement combinatoire : l’art de compter intelligemment, sans lister une à une toutes les possibilités. Ce chapitre, au cœur du programme de Terminale Spécialité Mathématiques, constitue aussi le socle indispensable des probabilités. Maîtriser le dénombrement combinatoire, c’est savoir choisir la bonne formule au bon moment — et c’est précisément l’objectif de ce cours.
Qu’est-ce que le dénombrement combinatoire ?
Définition. Dénombrer un ensemble fini, c’est déterminer son cardinal, c’est-à-dire le nombre d’éléments qu’il contient. L’analyse combinatoire regroupe l’ensemble des techniques mathématiques permettant ce comptage de façon systématique et rigoureuse, sans recourir à une énumération exhaustive.
On note le cardinal d’un ensemble \(E\) de deux façons équivalentes :
\text{Card}(E) \quad \text{ou} \quad |E|
\]
Exemple concret. L’ensemble des cartes d’un jeu de 32 cartes a un cardinal de 32. L’ensemble \(\mathbb{N}\) des entiers naturels, lui, n’est pas fini : il n’a pas de cardinal.
Pourquoi étudier le dénombrement combinatoire ?
Le dénombrement intervient partout où l’on cherche le nombre de configurations possibles : en probabilités (calculer des fréquences théoriques), en informatique (complexité algorithmique, cryptographie), en génétique (nombre de séquences d’ADN possibles), ou encore en théorie des jeux. Sans les outils du dénombrement combinatoire, il serait impossible de calculer la probabilité de gagner au loto ou de résoudre un Rubik’s Cube — dont les configurations possibles dépassent \(4{,}3 \times 10^{19}\).
Les deux principes fondamentaux du dénombrement
Avant d’aborder les formules, il faut assimiler deux règles de base qui gouvernent tout le dénombrement combinatoire. Elles paraissent simples, mais leur application correcte est décisive.
Le principe additif
Propriété (principe additif). Soient \(E_1, E_2, \ldots, E_p\) des ensembles finis deux à deux disjoints (sans élément en commun). Alors :
\text{Card}(E_1 \cup E_2 \cup \cdots \cup E_p) = \text{Card}(E_1) + \text{Card}(E_2) + \cdots + \text{Card}(E_p)
\]
Intuition. Si des groupes ne se croisent pas, on additionne leurs tailles. Dans une classe de 30 élèves, si 12 font du latin et 18 font de l’espagnol (sans personne dans les deux), la classe compte bien \(12 + 18 = 30\) élèves.
⚠ Attention ! Le principe additif n’est valable que si les ensembles sont disjoints. Si des élèves font les deux options, on commettrait une double comptage en additionnant directement. On utilise alors la formule d’inclusion-exclusion : \(\text{Card}(A \cup B) = \text{Card}(A) + \text{Card}(B) – \text{Card}(A \cap B)\).
Le principe multiplicatif
Propriété (principe multiplicatif). Si une expérience se décompose en \(p\) étapes successives et indépendantes, avec \(n_1\) choix à la première étape, \(n_2\) choix à la deuxième, …, \(n_p\) choix à la \(p\)-ième, alors le nombre total de résultats possibles est :
n_1 \times n_2 \times \cdots \times n_p
\]
Exemple classique. Un restaurant propose 3 entrées, 4 plats et 2 desserts. Le nombre de menus complets possibles est \(3 \times 4 \times 2 = 24\). C’est le principe multiplicatif — ou encore le cardinal du produit cartésien \(E \times P \times D\).
Les k-uplets : listes ordonnées avec répétition possible
Définition. Soit \(E\) un ensemble fini à \(n\) éléments et \(k\) un entier naturel non nul. Un \(k\)-uplet (ou \(k\)-liste) d’éléments de \(E\) est une suite ordonnée de \(k\) éléments de \(E\), avec répétitions autorisées.
Théorème. Le nombre de \(k\)-uplets d’éléments d’un ensemble à \(n\) éléments est :
n^k
\]
Preuve. On applique le principe multiplicatif : à chaque position (il y en a \(k\)), on dispose de \(n\) choix indépendants (la répétition est possible). On obtient donc \(\underbrace{n \times n \times \cdots \times n}_{k \text{ fois}} = n^k\).
Exemple. Un code PIN à 4 chiffres (de 0 à 9) correspond à un 4-uplet de l’ensemble \(\{0, 1, \ldots, 9\}\). Le nombre de codes possibles est \(10^4 = 10\,000\). C’est bien le nombre de codes de 0000 à 9999.
Application informatique. Un octet (8 bits) est un 8-uplet de \(\{0, 1\}\). Le nombre de valeurs représentables est \(2^8 = 256\), d’où les valeurs de 0 à 255 bien connues des développeurs.
La factorielle : définition et propriétés
Définition. Soit \(n\) un entier naturel. On appelle factorielle de \(n\), notée \(n!\), le produit de tous les entiers de 1 à \(n\) :
n! = 1 \times 2 \times 3 \times \cdots \times n \quad \text{avec la convention } 0! = 1
\]
Les premières valeurs à connaître :
| \(n\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| \(n!\) | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 3 628 800 |
La croissance de la factorielle est spectaculaire : \(20! \approx 2{,}4 \times 10^{18}\). Cette croissance explosive explique pourquoi certains problèmes combinatoires deviennent vite impossibles à résoudre par force brute.
Permutations : réordonner tous les éléments
Définition. Soit \(E = \{x_1, x_2, \ldots, x_n\}\) un ensemble à \(n\) éléments distincts. Une permutation de \(E\) est un \(n\)-uplet d’éléments tous distincts de \(E\) — autrement dit, un réarrangement de la totalité des éléments.
Théorème. Le nombre de permutations d’un ensemble à \(n\) éléments distincts est :
P_n = n!
\]
Preuve. On dispose de \(n\) choix pour placer le premier élément, puis de \(n-1\) pour le deuxième (l’élément déjà placé n’est plus disponible), puis \(n-2\) pour le troisième, et ainsi de suite jusqu’à 1 seul choix pour le dernier. Par le principe multiplicatif :
P_n = n \times (n-1) \times (n-2) \times \cdots \times 1 = n!
\]
Exemple. De combien de façons peut-on ranger 5 livres différents sur une étagère ? Il s’agit de compter les permutations de 5 éléments : \(5! = 120\) façons.
Interprétation visuelle
Arrangements : choisir k éléments dans un ordre précis
Définition. Soit \(E\) un ensemble à \(n\) éléments et \(k\) un entier tel que \(1 \leq k \leq n\). Un arrangement de \(k\) éléments parmi \(n\) (aussi appelé \(k\)-uplet d’éléments distincts) est une suite ordonnée de \(k\) éléments de \(E\) tous distincts (sans répétition, l’ordre compte).
Théorème. Le nombre d’arrangements de \(k\) éléments parmi \(n\) est noté \(A_n^k\) et vaut :
A_n^k = \frac{n!}{(n-k)!} = n \times (n-1) \times \cdots \times (n-k+1)
\]
C’est le produit de \(k\) facteurs consécutifs décroissants à partir de \(n\).
Preuve. On choisit successivement \(k\) éléments distincts. Pour le 1er : \(n\) choix. Pour le 2e : \(n-1\) (l’élément choisi est exclu). Pour le \(i\)-ième : \(n-i+1\) choix. Le principe multiplicatif donne :
A_n^k = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}
\]
En particulier, si \(k = n\), on retrouve \(A_n^n = n!\), c’est-à-dire le nombre de permutations.
Exemple classique : le tiercé. Dans une course de 15 chevaux, combien de tiercés dans l’ordre sont possibles ? Il s’agit d’un arrangement de 3 parmi 15 :
A_{15}^3 = 15 \times 14 \times 13 = 2\,730
\]
⚠ L’ordre compte ! Dans un arrangement, le podium (Or, Argent, Bronze) = (Cheval A, B, C) est différent de (B, A, C). Si l’ordre n’importe pas, il faut utiliser les combinaisons (voir section suivante).
Combinaisons et coefficient binomial : choisir sans tenir compte de l’ordre
Définition. Soit \(E\) un ensemble à \(n\) éléments et \(k\) un entier tel que \(0 \leq k \leq n\). Une combinaison de \(k\) éléments parmi \(n\) est un sous-ensemble de \(E\) comportant exactement \(k\) éléments. L’ordre n’a aucune importance.
Théorème : Coefficient binomial. Le nombre de combinaisons de \(k\) éléments parmi \(n\) est noté \(\binom{n}{k}\) (lu « \(k\) parmi \(n\) ») et vaut :
\binom{n}{k} = \frac{n!}{k!\,(n-k)!} = \frac{A_n^k}{k!}
\]
Preuve intuitive
Partons du nombre d’arrangements \(A_n^k\). Chaque combinaison (sous-ensemble non ordonné de \(k\) éléments) est comptée autant de fois qu’il y a de façons d’ordonner ses \(k\) éléments, c’est-à-dire \(k!\) fois. On divise donc :
\binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!\,(n-k)!}
\]
Propriétés essentielles du coefficient binomial
- Symétrie : \(\displaystyle\binom{n}{k} = \binom{n}{n-k}\). Choisir \(k\) éléments revient à choisir les \(n-k\) éléments qu’on exclut.
- Cas limites : \(\displaystyle\binom{n}{0} = 1\) et \(\binom{n}{n} = 1\).
- Relation de Pascal :\[
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
\]Cette relation permet de construire le triangle de Pascal.
- Somme des coefficients binomiaux :\[
\sum_{k=0}^{n} \binom{n}{k} = 2^n
\]Ce résultat exprime que le nombre total de sous-ensembles d’un ensemble à \(n\) éléments est \(2^n\).
Le triangle de Pascal
Le triangle de Pascal est une représentation visuelle des coefficients binomiaux. Chaque coefficient est la somme des deux coefficients situés au-dessus de lui (relation de Pascal) :
Exemple. On tire simultanément 3 cartes d’un jeu de 32. Combien de mains différentes peut-on obtenir ?
\binom{32}{3} = \frac{32!}{3!\,29!} = \frac{32 \times 31 \times 30}{3 \times 2 \times 1} = \frac{29\,760}{6} = 4\,960
\]
Il existe donc 4 960 mains de 3 cartes distinctes — sans qu’importe l’ordre dans lequel on les reçoit.
Tableau récapitulatif : choisir le bon outil en dénombrement combinatoire
La grande difficulté du dénombrement est d’identifier le type d’objet à compter. Voici une grille de lecture :
| Situation | L’ordre compte ? | Répétition ? | Formule | Nom |
|---|---|---|---|---|
| Choisir \(k\) éléments parmi \(n\) | Non | Non | \(\displaystyle\binom{n}{k} = \dfrac{n!}{k!(n-k)!}\) | Combinaison |
| Choisir \(k\) éléments parmi \(n\) | Oui | Non | \(\displaystyle A_n^k = \dfrac{n!}{(n-k)!}\) | Arrangement |
| Réordonner \(n\) éléments | Oui | Non | \(n!\) | Permutation |
| Former des listes de \(k\) éléments | Oui | Oui | \(n^k\) | \(k\)-uplet |
⚠ Méthode de questionnement. Face à tout problème de dénombrement combinatoire, posez-vous systématiquement ces deux questions : (1) L’ordre des éléments choisis a-t-il de l’importance dans le contexte du problème ? (2) Un même élément peut-il être sélectionné plusieurs fois ? Les réponses déterminent directement la formule à utiliser.
L’essentiel du dénombrement combinatoire
Le dénombrement combinatoire repose sur quelques idées fondamentales : les deux principes de base (additif et multiplicatif), la factorielle comme brique de calcul, et trois objets centraux — les permutations, les arrangements et les combinaisons. La clé pour maîtriser ce chapitre est d’apprendre à poser les bonnes questions face à chaque problème : l’ordre compte-t-il ? Y a-t-il répétition ? La réponse à ces deux questions suffit à choisir la bonne formule.
Les coefficients binomiaux, au cœur des combinaisons, réapparaissent naturellement dans le triangle de Pascal, dans la formule du binôme de Newton, et dans la loi binomiale en probabilités. Maîtriser le dénombrement combinatoire, c’est donc poser des bases solides pour toute la suite du programme de mathématiques.