Dénombrement : listes, arrangements, combinaisons

Dénombrer, c'est compter sans énumérer. Toutes les formules du chapitre découlent de deux principes et de deux questions qu'on se pose avant d'écrire un nombre : l'ordre compte-t-il ? Les répétitions sont-elles permises ?

Les deux principes.

• Principe additif : si $A$ et $B$ sont finis et disjoints, $\mathrm{card}(A \cup B) = \mathrm{card}\,A + \mathrm{card}\,B$. S'ils ne le sont pas, on retranche ce qui a été compté deux fois : $\mathrm{card}(A \cup B) = \mathrm{card}\,A + \mathrm{card}\,B - \mathrm{card}(A \cap B)$.
• Principe multiplicatif : $\mathrm{card}(A \times B) = \mathrm{card}\,A \times \mathrm{card}\,B$. Plus concrètement, si un choix se fait en deux étapes, avec $p$ possibilités pour la première et, quelle que soit la première, $q$ pour la seconde, il y a $pq$ choix.

Les quatre modèles. On choisit $k$ objets parmi $n$ objets distincts.

• Une liste (ou $k$-uplet) de $n^{k}$ : un code de $4$ chiffres compte $10^{4} = 10\,000$ possibilités ($10$ choix à chaque position, indépendants).
• Un arrangement : on remplit $k$ places distinctes sans réutiliser un objet, $n$ choix, puis $n - 1$, …, puis $n - k + 1$. Pour $k = n$, ce sont les permutations : $n!$.
• Une combinaison est une partie à $k$ éléments : l'ordre n'existe pas. Chaque partie correspond à exactement $k!$ arrangements (les $k!$ façons de l'ordonner), d'où

Exemple : une délégation de $4$ personnes dans une association de $25$ membres : $A_{25}^{4} = 25 \times 24 \times 23 \times 22 = 303\,600$ listes ordonnées, mais chaque délégation y apparaît $4! = 24$ fois, donc $\dbinom{25}{4} = \dfrac{303\,600}{24} = 12\,650$ délégations.

La bonne question. « Si j'échange deux éléments de ma configuration, ai-je obtenu une configuration différente ? » Oui : l'ordre compte. Non : il ne compte pas. Un podium (premier, deuxième, troisième) est ordonné ; une délégation sans rôles ne l'est pas.

Objets indiscernables. Le nombre de mots distincts obtenus en permutant les lettres d'un mot de $n$ lettres où une lettre figure $m_1$ fois, une autre $m_2$ fois, etc., vaut

Raison : si l'on marquait les lettres répétées ($\mathrm{P}_1$, $\mathrm{P}_2$), on aurait $n!$ permutations ; mais chaque mot réel en représente $m_1!\,m_2!\cdots$, obtenus en échangeant entre elles les copies d'une même lettre. Pour PAPOTER : $7$ lettres, dont deux P et cinq lettres distinctes, donc $\dfrac{7!}{2!} = 2\,520$ anagrammes (le mot lui-même compris).

Choisir, puis choisir. Quand une configuration se décrit par plusieurs choix indépendants, on multiplie. Une main de $5$ cartes d'un jeu de $52$ contenant exactement $2$ as : on choisit les $2$ as parmi $4$, et les $3$ autres cartes parmi les $48$ qui ne sont pas des as :

Le mot « exactement » interdit de prendre les $3$ autres cartes parmi les $50$ restantes : on compterait des mains à $3$ ou $4$ as, et plusieurs fois.

Formule de Pascal. Pour $1 \le k \le n - 1$ :

Preuve combinatoire : on distingue un élément $a$ ; une partie à $k$ éléments le contient (il reste $k - 1$ éléments à choisir parmi $n - 1$) ou ne le contient pas ($k$ parmi $n - 1$). Ces deux familles sont disjointes : principe additif. Exemple : $\dbinom{5}{2} + \dbinom{5}{3} = 10 + 10 = 20 = \dbinom{6}{3}$. La symétrie $\dbinom{n}{k} = \dbinom{n}{n - k}$ vient de même du passage au complémentaire.

Binôme de Newton. Pour tous $a$, $b$ complexes et $n \in \mathbb{N}$,

En développant le produit de $n$ facteurs $(a + b)$, le terme $a^{k}b^{n - k}$ apparaît autant de fois qu'il y a de façons de choisir les $k$ facteurs qui fournissent $a$ : $\dbinom{n}{k}$. Exemple : $(x + 2)^{4} = x^{4} + 8x^{3} + 24x^{2} + 32x + 16$. Avec $a = b = 1$ : $\sum_{k} \dbinom{n}{k} = 2^{n}$, le nombre de parties d'un ensemble à $n$ éléments.

Réunion de deux ensembles. Sur $90$ adhérents, $31$ font de la natation, $27$ du vélo, $9$ les deux. Ceux qui pratiquent au moins une activité : $31 + 27 - 9 = 49$ ; aucune : $90 - 49 = 41$. Sans retrancher l'intersection, on surestimerait le premier nombre et sous-estimerait le second de $9$ : les $9$ sportifs des deux activités auraient été comptés deux fois.

Énoncé.

1. $20$ coureurs prennent le départ, sans ex æquo possible. Combien y a-t-il de podiums (trois premières places) possibles ?
2. Combien de codes à $5$ chiffres (de $0$ à $9$) existe-t-il ?
3. Combien de délégations de $4$ personnes peut-on former dans une association de $25$ membres ?
4. Un code à $5$ chiffres tous distincts : combien de possibilités ?

---

1. Ordre : oui. Répétition : non. Échanger le premier et le deuxième donne un autre classement ; un coureur n'occupe qu'une place. Arrangements :

2. Ordre : oui. Répétition : oui. $12345$ et $54321$ sont deux codes ; un chiffre peut revenir. Listes : $10^{5} = 100\,000$.

3. Ordre : non. Répétition : non. Une délégation sans rôles est une partie de l'association :

Le numérateur seul ($303\,600$) compterait chaque délégation $24$ fois.

4. Ordre : oui. Répétition : non. $A_{10}^{5} = 10 \times 9 \times 8 \times 7 \times 6 = 30\,240$. On compare utilement avec la question 2 : $100\,000 - 30\,240 = 69\,760$ codes ont au moins un chiffre répété, soit plus de deux sur trois. Passer de « avec » à « sans » répétition divise ici le résultat par plus de trois.

Lecture. Les quatre réponses sont différentes parce que les deux questions — ordre, répétition — ont reçu quatre combinaisons de réponses. La formule se choisit après ces deux réponses, jamais avant.

Figure (fig.math.binomial-tree-and-bars, figure programmatique de la leçon de terminale sur la loi binomiale, réutilisée ici parce que son arbre est un dénombrement dessiné) : à gauche, un arbre à trois niveaux, chaque nœud ouvrant deux branches $S$ et $E$ ; huit chemins en tout, dont trois — $SSE$, $SES$, $ESS$ — contiennent exactement deux succès et sont tracés en trait épais. À droite, le diagramme en bâtons de la loi $\mathcal{B}(10\,;\,0{,}4)$.

Pour cette leçon, oubliez les probabilités écrites sur les branches et ne gardez que la structure.

• Huit chemins : chaque chemin est une liste de longueur $3$ sur l'alphabet $\{S, E\}$, donc $2^{3} = 8$ — principe multiplicatif, deux choix à chaque niveau.
• Trois chemins épais : un chemin à deux succès est entièrement déterminé par les positions de ses deux $S$, c'est-à-dire par une partie à $2$ éléments de $\{1, 2, 3\}$ : $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$. D'où $\dbinom{3}{2} = 3$. C'est la définition du coefficient binomial, dessinée.
• La somme des comptes : $\dbinom{3}{0} + \dbinom{3}{1} + \dbinom{3}{2} + \dbinom{3}{3} = 1 + 3 + 3 + 1 = 8 = 2^{3}$ — le binôme de Newton avec $a = b = 1$.
• Les onze bâtons de droite correspondent aux onze valeurs de $k$ ; le nombre de chemins de l'arbre à dix niveaux qui y mènent est $\dbinom{10}{k}$, symétrique en $k$ et $10 - k$, maximal au milieu.

Ce que la figure ne montre pas : les situations où l'ordre compte sans répétition (arrangements), et la formule de Pascal, qu'on lirait sur l'arbre en regardant la dernière branche : un chemin de longueur $3$ à deux succès finit par $S$ (il reste un succès à placer dans les deux premiers niveaux) ou par $E$ (il en reste deux), soit $\dbinom{2}{1} + \dbinom{2}{2} = 2 + 1 = 3$.