M17 — Dénombrement

Objectif du chapitre. Maîtriser le comptage des objets finis : les p-listes, les arrangements, les permutations, les combinaisons, le cardinal de l'ensemble des parties, la formule de Pascal (interprétation combinatoire) et le principe des tiroirs. L'objectif est de savoir choisir entre liste, arrangement et combinaison, et de compter des mains, des mots, des anagrammes sans erreur.

Notions

1. Cardinal, réunion disjointe, produit cartésien

Soient $A$ et $B$ deux ensembles finis.

• Cardinal : $\lvert A \rvert$ est le nombre d'éléments de $A$.
• Réunion disjointe : si $A \cap B = \varnothing$, alors $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert$ (principe d'addition).
• Produit cartésien : $\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert$ (principe de multiplication).

Ces deux principes sont les outils de base du dénombrement : on décompose un dénombrement en cas disjoints (addition) et on compte les choix successifs (multiplication).

2. p-listes, arrangements, permutations

Soit $E$ un ensemble de cardinal $n$.

• p-liste (ou liste de $p$ éléments) : une suite ordonnée $(x_1, \dots, x_p)$ d'éléments de $E$, avec répétition autorisée. Nombre de p-listes : $n^p$.
• Arrangement de $p$ éléments parmi $n$ : une suite ordonnée $(x_1, \dots, x_p)$ d'éléments distincts de $E$ (ordre compte, sans répétition). Nombre d'arrangements :

$$A_n^p = \frac{n!}{(n - p)!} = n \cdot (n - 1) \cdot \dots \cdot (n - p + 1).$$

• Permutation de $n$ éléments : un arrangement de $n$ éléments parmi $n$ (ordre compte, tous les éléments). Nombre de permutations : $P_n = n!$.

Relation. $A_n^p = \dfrac{n!}{(n - p)!}$ ; en particulier $A_n^n = n!$ (les permutations sont les arrangements complets).

Exemple (mots). Combien de mots de 4 lettres peut-on former avec les 26 lettres de l'alphabet ?

• Répétition autorisée (p-listes) : $26^4 = 456\,976$ mots.
• Sans répétition (arrangements) : $A_{26}^4 = 26 \cdot 25 \cdot 24 \cdot 23 = 358\,800$ mots.

Exemple (places assises). Combien de façons d'asseoir 5 personnes sur 8 chaises en ligne ? C'est un arrangement de 5 éléments parmi 8 : $A_8^5 = 8! / 3! = 67\,200$.

3. Applications entre ensembles finis

Soient $E$ de cardinal $m$ et $F$ de cardinal $n$ (avec $m \leq n$).

• Applications $E \to F$ : $n^m$ (chaque élément de $E$ a $n$ images possibles).
• Applications injectives $E \to F$ : $A_n^m = \dfrac{n!}{(n - m)!}$ (on choisit $m$ images distinctes, l'ordre compte).
• Applications surjectives $E \to F$ : $\displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n - k)^m$ (formule d'inclusion-exclusion) ; en particulier si $m = n$, il y a $n!$ applications bijectives.

(formule complète énoncée en §8 de ce chapitre).

• Applications bijectives $E \to F$ : $n!$ si $m = n$ (les permutations), $0$ sinon.

Interprétation. Le nombre d'applications injectives de $E$ dans $F$ est le nombre de façons d'étiqueter $m$ éléments de $F$ par les éléments de $E$ sans répétition : c'est exactement $A_n^m$.

4. Combinaisons

Une combinaison de $p$ éléments parmi $n$ est une partie de $E$ de cardinal $p$ (ordre ne compte pas, sans répétition). Nombre de combinaisons :

$$\binom{n}{p} = \frac{n!}{p!\, (n - p)!}.$$

Relation avec les arrangements. $\binom{n}{p} = \dfrac{A_n^p}{p!}$ : une combinaison est un arrangement de $p$ éléments, modulo l'ordre (on divise par $p!$ le nombre de permutations de ces $p$ éléments).

Propriétés des coefficients binomiaux.

• Symétrie : $\binom{n}{p} = \binom{n}{n - p}$.
• Formule de Pascal : $\binom{n + 1}{p} = \binom{n}{p} + \binom{n}{p - 1}$.
• Somme : $\displaystyle\sum_{p = 0}^{n} \binom{n}{p} = 2^n$ (cardinal de l'ensemble des parties).

5. Interprétation combinatoire de la formule de Pascal

Énoncé. $\binom{n + 1}{p} = \binom{n}{p} + \binom{n}{p - 1}$.

Démonstration combinatoire. Soit $E$ un ensemble de $n + 1$ éléments, et $a \in E$ un élément fixé. Les parties de $E$ de cardinal $p$ se décomposent en deux cas disjoints :

1. Les parties contenant $a$ : on choisit $p - 1$ éléments parmi les $n$ restants, soit $\binom{n}{p - 1}$ parties.
2. Les parties ne contenant pas $a$ : on choisit $p$ éléments parmi les $n$ restants, soit $\binom{n}{p}$ parties.

Par le principe d'addition, le nombre total de parties de cardinal $p$ est $\binom{n}{p} + \binom{n}{p - 1}$.

6. Cardinal de l'ensemble des parties

L'ensemble $\mathcal{P}(E)$ des parties de $E$ (avec $\lvert E \rvert = n$) a pour cardinal $2^n$.

Démonstration. Chaque élément de $E$ est soit dans la partie, soit hors de la partie : $2$ choix par élément, donc $2^n$ parties au total. Équivalent : $\lvert \mathcal{P}(E) \rvert = \sum_{p = 0}^{n} \binom{n}{p} = 2^n$ (somme des coefficients binomiaux).

7. Principe des tiroirs

Énoncé. Si on répartit $n + 1$ objets dans $n$ tiroirs, alors au moins un tiroir contient au moins deux objets.

Généralisation. Si on répartit $n$ objets dans $k$ tiroirs, alors au moins un tiroir contient au moins $\left\lceil \dfrac{n}{k} \right\rceil$ objets.

Application. Le principe des tiroirs est l'outil de base des démonstrations par l'absurde en combinatoire : pour montrer qu'il existe deux objets avec une propriété commune, on suppose le contraire et on aboutit à une contradiction de comptage.

Exemple. Parmi $n + 1$ entiers, il en existe deux dont la différence est divisible par $n$ (les $n$ restes modulo $n$ sont les « tiroirs » ; deux entiers ont le même reste, donc leur différence est divisible par $n$).

8. Formule d'inclusion-exclusion (complément)

Soient $A_1, \dots, A_k$ des sous-ensembles d'un ensemble fini $E$. Le principe d'inclusion-exclusion (cas général $k$ quelconque — complément, l'annexe s'arrête à la réunion disjointe et au crible $k = 2$) donne le cardinal de la réunion :

$$\lvert A_1 \cup \dots \cup A_k \rvert = \sum_{i} \lvert A_i \rvert - \sum_{i < j} \lvert A_i \cap A_j \rvert + \sum_{i < j < \ell} \lvert A_i \cap A_j \cap A_\ell \rvert - \dots + (-1)^{k+1} \lvert A_1 \cap \dots \cap A_k \rvert.$$

Cas $k = 2$. $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$ (on soustrait l'intersection comptée deux fois).

Cas $k = 3$. $\lvert A \cup B \cup C \rvert = \lvert A \rvert + \lvert B \rvert + \lvert C \rvert - \lvert A \cap B \rvert - \lvert A \cap C \rvert - \lvert B \cap C \rvert + \lvert A \cap B \cap C \rvert$.

Application (complément). Le nombre d'applications surjectives $E \to F$ (avec $\lvert E \rvert = m$, $\lvert F \rvert = n$) est $\displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n - k)^m$ : on compte les applications qui « ratent » au moins un élément de $F$, et on applique inclusion-exclusion. C'est aussi le nombre de mots de longueur $m$ sur un alphabet de $n$ lettres utilisant toutes les lettres.

9. Anagrammes avec répétitions

Le nombre d'anagrammes d'un mot de $n$ lettres, où la lettre $a_i$ apparaît $m_i$ fois (avec $\sum m_i = n$), est

$$\frac{n!}{m_1!\, m_2!\, \dots\, m_k!}.$$

Justification. Sans répétition, il y a $n!$ anagrammes ; mais les lettres identiques sont indistinguables, donc on a compté chaque anagramme $m_1! \cdot m_2! \cdot \dots \cdot m_k!$ fois (les permutations des lettres identiques). On divise par ce facteur.

Exemple. Le mot « PRÉPA » (5 lettres, $P$ deux fois) a $\dfrac{5!}{2!} = 60$ anagrammes. Le mot « MATHÉMATIQUES » (13 lettres, $M$, $A$, $T$, $E$ deux fois) a $\dfrac{13!}{(2!)^4}$ anagrammes.

Capacités exigibles

• M17.combinatoire — Choisir entre liste, arrangement et combinaison : identifier si l'ordre compte (liste/arrangement) ou non (combinaison), si la répétition est autorisée (liste) ou non (arrangement/combinaison), et appliquer la formule correspondante.

Pièges classiques

• Arrangement = l'ordre compte, combinaison = l'ordre ne compte pas : c'est la distinction essentielle ; un arrangement est une suite ordonnée, une combinaison est une partie (non ordonnée).
• Les anagrammes avec répétitions divisent par les factorielles des multiplicités : on divise par $m_i!$ pour chaque lettre $a_i$ de multiplicité $m_i$ ; oublier cette division donne un résultat trop grand.
• p-liste : répétition autorisée : le nombre de p-listes est $n^p$ (pas $A_n^p$) ; la répétition est autorisée dans une p-liste, interdite dans un arrangement.
• Formule de Pascal : $\binom{n+1}{p} = \binom{n}{p} + \binom{n}{p-1}$ : il ne faut pas confondre avec $\binom{n}{p} + \binom{n}{p+1}$ (faux) ; l'interprétation combinatoire (contient $a$ / ne contient pas $a$) est l'outil de mémorisation.
• Principe des tiroirs : c'est un outil de démonstration, pas de comptage : il ne donne pas le nombre exact d'objets dans un tiroir, mais un minorant (au moins $\lceil n/k \rceil$) ; il sert à prouver l'existence, pas à compter.
• Combinaisons : $\binom{n}{p} = 0$ si $p > n$ : par convention, on ne peut pas choisir plus d'éléments qu'il n'y en a ; la formule $\dfrac{n!}{p!(n-p)!}$ n'est pas définie pour $p > n$.

Graphe de référence

Le nombre de combinaisons $\binom{n}{p}$ en fonction de $n$ (pour $p = n/2$) croît comme $\sqrt{\dfrac{2}{\pi}}\,\dfrac{2^n}{\sqrt{n}}$ (loi de Stirling, complément hors programme) ; la courbe $\binom{n}{\lfloor n/2 \rfloor}$ illustre la croissance combinatoire (exponentielle amortie par $\sqrt{n}$).

Pour aller plus loin

Annales utilisables sur ce chapitre (§4 de l'annexe Ressources, exercices et annales) : CCINP et e3a (exercice de probabilités, souvent 100 % PCSI).

Voir aussi Ressources, exercices et annales pour les manuels recommandés et les banques d'exercices gratuites.