Combinatoire et dénombrement

À l'été 1654, deux des plus grands esprits de France échangent des lettres à propos… de jeux de dés et de paris. Antoine Gombaud, chevalier de Méré, joueur mondain et fin observateur, a soumis à Blaise Pascal des problèmes qui le tourmentent : combien de lancers de deux dés faut-il pour avoir intérêt à parier sur un double six ? Et surtout, comment partager équitablement les mises d'une partie interrompue avant son terme ? Pascal en discute par courrier avec Pierre de Fermat, magistrat à Toulouse, et de cette correspondance naît une idée révolutionnaire : pour raisonner sur le hasard, il faut d'abord savoir compter — compter les issues possibles, compter les issues favorables, sans jamais les énumérer une à une quand elles se chiffrent en milliers. Cette science du comptage intelligent s'appelle la combinatoire, et c'est elle qui a permis la naissance du calcul des probabilités. La même année, Pascal rédige son Traité du triangle arithmétique, consacré au tableau de nombres que nous appelons aujourd'hui « triangle de Pascal ». L'histoire est ici injuste : ce triangle était connu du mathématicien perse al-Karaji dès le Xe siècle, des savants indiens qui étudiaient les mètres poétiques, puis du Chinois Zhu Shijie qui le publie en 1303 — trois siècles et demi avant Pascal. Ce chapitre reconstruit tout cet édifice, des principes de comptage les plus élémentaires jusqu'au triangle et à ses propriétés, avec un fil conducteur constant : avant de compter, toujours se demander ce que l'on compte.

Ensembles finis, cardinal et produit cartésien

La combinatoire compte des objets. Pour le faire proprement, il faut d'abord un vocabulaire précis sur les collections d'objets : celui des ensembles.

Rappelons qu'un ensemble ne tient aucun compte de l'ordre ni des répétitions : $\{a;b;c\}$, $\{c;a;b\}$ et $\{a;b;c;a\}$ désignent exactement le même ensemble. Deux ensembles $A$ et $B$ sont dits disjoints lorsqu'ils n'ont aucun élément commun, c'est-à-dire lorsque $A\cap B=\mathrm{\varnothing }$ ; leur réunion $A\cup B$ est alors appelée réunion disjointe. Plus généralement, des ensembles $A_1,A_2,\dots ,A_m$ sont deux à deux disjoints lorsque deux quelconques d'entre eux sont toujours disjoints.

À côté des ensembles, la combinatoire manipule un second type de collection, où l'ordre compte : les listes.

Les deux principes du dénombrement

Tout le chapitre repose sur deux principes d'une simplicité trompeuse. Le premier dit qu'on peut compter une collection en la découpant en paquets qui ne se recouvrent pas.

C'est le bon sens même : si une classe réunit $12$ élèves qui font de l'espagnol et $18$ qui font de l'allemand, et si aucun élève ne fait les deux, la classe compte $12+18=30$ élèves. L'hypothèse « deux à deux disjoints » est essentielle : si des élèves suivaient les deux langues, ils seraient comptés deux fois. Le second principe gouverne les choix successifs.

Pour s'en convaincre, imaginons un tableau : pour former un couple $(a;b)$, on choisit la ligne $a$ parmi $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)$ lignes, puis la colonne $b$ parmi $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)$ colonnes ; le tableau contient bien $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)\times \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)$ cases, une par couple. On peut aussi voir chaque couple comme un chemin dans un arbre : $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)$ branches au premier niveau, chacune suivie de $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)$ branches au second.

Nombre de $k$-uplets d'un ensemble à $n$ éléments

Le principe multiplicatif appliqué à $A^k$ donne immédiatement le premier grand résultat du chapitre.

Démonstration. Un $k$-uplet de $A$ se construit par $k$ choix successifs : le premier élément parmi $n$, le deuxième parmi $n$ (les répétitions sont permises, le choix précédent ne retire rien), et ainsi de suite jusqu'au $k$-ième, toujours parmi $n$. D'après le principe multiplicatif, il y a $n\times n\times \cdots \times n=n^k$ possibilités. $\mathrm{\square }$

Nombre de parties d'un ensemble

Une partie (ou sous-ensemble) d'un ensemble $E$ est un ensemble dont tous les éléments appartiennent à $E$. Par exemple, les parties de $\{a;b\}$ sont $\mathrm{\varnothing }$, $\{a\}$, $\{b\}$ et $\{a;b\}$ : il y en a $4$, en comptant l'ensemble vide et $E$ lui-même. Ce compte de $4=2^2$ n'est pas un hasard.

Démonstration. Soit $E=\{e_1;e_2;\dots ;e_n\}$. À chaque partie $F$ de $E$, associons le $n$-uplet de $\{0;1\}$ dont le $i$-ième terme vaut $1$ si $e_i\in F$ et $0$ sinon. Par exemple, pour $n=3$, la partie $\{e_1;e_3\}$ correspond au triplet $(1;0;1)$ et l'ensemble vide au triplet $(0;0;0)$. Cette correspondance associe à toute partie un unique $n$-uplet, et réciproquement tout $n$-uplet de $\{0;1\}$ décrit une unique partie (on prend exactement les éléments marqués d'un $1$) : parties de $E$ et $n$-uplets de $\{0;1\}$ sont donc en même nombre. Or l'ensemble $\{0;1\}$ a $2$ éléments, si bien que le nombre de ses $n$-uplets est $2^n$ d'après la propriété précédente. $\mathrm{\square }$

Ce résultat est un carrefour du programme : le même nombre $2^n$ compte quatre familles d'objets en apparence très différentes, et savoir passer de l'une à l'autre est une compétence attendue.

L'arbre ci-dessus illustre le cas $n=3$ : à chaque niveau, le chemin se sépare en deux branches ($0$ ou $1$), et les $2\times 2\times 2=8$ chemins complets correspondent aux $8$ mots de longueur $3$, donc aux $8$ parties d'un ensemble à $3$ éléments.

$k$-uplets d'éléments distincts et permutations

Modifions le modèle du tirage : cette fois, on tire sans remise. Un élément déjà choisi ne peut plus l'être — les termes de la liste doivent être distincts.

Démonstration. On construit la liste par choix successifs : $n$ possibilités pour le premier élément ; le deuxième doit être différent du premier, il reste $n-1$ possibilités ; puis $n-2$ pour le troisième, et ainsi de suite. Au $k$-ième choix, $k-1$ éléments sont déjà pris : il reste $n-(k-1)=n-k+1$ possibilités. Le principe multiplicatif donne le produit annoncé. Et si $k>n$, la construction s'enraye avant la fin : les éléments viennent à manquer, aucun $k$-uplet d'éléments distincts n'existe. $\mathrm{\square }$

Ces listes sans répétition sont parfois appelées arrangements dans le vocabulaire usuel ; ce mot n'est pas indispensable, l'expression « $k$-uplet d'éléments distincts » dit exactement la même chose. Le cas particulier $k=n$ — ranger tous les éléments — fait apparaître un produit qui mérite son propre nom.

Démonstration. C'est le cas $k=n$ de la propriété précédente : le nombre cherché vaut $n(n-1)\cdots (n-n+1)=n(n-1)\cdots 2\times 1=n!$. $\mathrm{\square }$

Combinaisons

Dernier modèle, le plus important pour la suite du programme : on choisit $k$ éléments parmi $n$, sans répétition, mais cette fois sans tenir compte de l'ordre. Choisir $3$ délégués dans une classe, c'est désigner un ensemble de $3$ élèves : les nommer dans un ordre ou un autre ne change rien.

Démonstration. Comptons de deux façons les $k$-uplets d'éléments distincts d'un ensemble à $n$ éléments. D'une part, on sait qu'il y en a $n(n-1)\cdots (n-k+1)$. D'autre part, on peut construire un tel $k$-uplet en deux temps : choisir d'abord la partie à $k$ éléments qui le compose — ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}$ possibilités — puis ranger ces $k$ éléments dans un ordre — $k!$ permutations possibles. Le principe multiplicatif donne alors

$$n(n-1)\cdots (n-k+1)=\left(\genfrac{}{}{0px}{}{n}{k}\right)\times k!,$$

d'où la première formule en divisant par $k!$. Pour la seconde, on prolonge le produit du numérateur : $n(n-1)\cdots (n-k+1)={\displaystyle \frac{n!}{(n-k)!}}$, car les facteurs de $n-k$ à $1$ se simplifient. $\mathrm{\square }$

Le lien avec la section sur les $2^n$ est direct : une partie à $k$ éléments d'un ensemble à $n$ éléments correspond à un mot de longueur $n$ sur l'alphabet $\{0;1\}$ comportant exactement $k$ lettres $1$. Ainsi ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}$ compte aussi les mots binaires de longueur $n$ ayant $k$ fois la lettre $1$ — il suffit de choisir les $k$ positions des $1$ parmi les $n$ positions — ou encore, sur l'arbre binaire, les chemins comportant exactement $k$ succès.

Propriétés des coefficients binomiaux

Certaines valeurs des coefficients binomiaux se lisent directement sur leur signification combinatoire, sans aucun calcul.

En effet : un ensemble à $n$ éléments n'a qu'une seule partie à $0$ élément (l'ensemble vide) et une seule partie à $n$ éléments (lui-même) ; ses parties à $1$ élément sont les $n$ singletons ; et pour les paires, la formule donne ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{2}\right)}={\displaystyle \frac{n(n-1)}{2!}}={\displaystyle \frac{n(n-1)}{2}}$ — c'est le nombre de poignées de main échangées quand $n$ personnes se saluent toutes deux à deux.

Démonstration. Par le calcul. La formule factorielle donne

$$\left(\genfrac{}{}{0px}{}{n}{n-k}\right)={\displaystyle \frac{n!}{(n-k)!(n-(n-k))!}}={\displaystyle \frac{n!}{(n-k)!k!}}=\left(\genfrac{}{}{0px}{}{n}{k}\right),$$

car échanger les deux facteurs du dénominateur ne change pas le produit.

Par interprétation combinatoire. Choisir une partie à $k$ éléments d'un ensemble à $n$ éléments, c'est exactement choisir les $n-k$ éléments qu'on laisse de côté : à chaque partie à $k$ éléments correspond son complémentaire, qui est une partie à $n-k$ éléments, et cette correspondance est parfaite (deux parties distinctes ont des complémentaires distincts, et toute partie à $n-k$ éléments est le complémentaire d'une partie à $k$ éléments). Les deux familles ont donc le même cardinal. $\mathrm{\square }$

La propriété suivante est le cœur du chapitre : elle relie chaque coefficient binomial aux deux coefficients « du cran précédent », et permet de les calculer tous de proche en proche.

Démonstration (exigible) — par le calcul. Réduisons la somme de droite au même dénominateur $k!(n-k)!$ :

$$\left(\genfrac{}{}{0px}{}{n-1}{k}\right)={\displaystyle \frac{(n-1)!}{k!(n-1-k)!}}={\displaystyle \frac{(n-1)!(n-k)}{k!(n-k)!}},$$

en multipliant numérateur et dénominateur par $n-k$, puisque $(n-1-k)!\times (n-k)=(n-k)!$. De même,

$$\left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)={\displaystyle \frac{(n-1)!}{(k-1)!(n-k)!}}={\displaystyle \frac{(n-1)!k}{k!(n-k)!}},$$

en multipliant cette fois par $k$, puisque $(k-1)!\times k=k!$. En additionnant :

$$\left(\genfrac{}{}{0px}{}{n-1}{k}\right)+\left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)={\displaystyle \frac{(n-1)!(n-k)+(n-1)!k}{k!(n-k)!}}={\displaystyle \frac{(n-1)!((n-k)+k)}{k!(n-k)!}}={\displaystyle \frac{(n-1)!\times n}{k!(n-k)!}}={\displaystyle \frac{n!}{k!(n-k)!}}=\left(\genfrac{}{}{0px}{}{n}{k}\right)\mathrm{.}\mathrm{\square }$$

Démonstration (exigible) — par une méthode combinatoire. Soit $E$ un ensemble à $n$ éléments, et fixons un élément $a$ de $E$. Les parties à $k$ éléments de $E$ se répartissent en deux catégories disjointes, selon qu'elles contiennent $a$ ou non.

• Les parties qui contiennent $a$ : pour en construire une, il reste à choisir les $k-1$ autres éléments parmi les $n-1$ éléments de $E$ distincts de $a$. Il y en a donc ${\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)}$.
• Les parties qui ne contiennent pas $a$ : ce sont exactement les parties à $k$ éléments de l'ensemble $E\setminus \{a\}$, qui possède $n-1$ éléments. Il y en a ${\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{k}\right)}$.

Toute partie à $k$ éléments de $E$ appartient à une catégorie et une seule : le principe additif donne

$$\left(\genfrac{}{}{0px}{}{n}{k}\right)=\left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0px}{}{n-1}{k}\right)\mathrm{.}\mathrm{\square }$$

La relation de Pascal fournit une machine à calculer tous les coefficients binomiaux : on les dispose en triangle, la ligne $n$ contenant les nombres ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{0}\right)},{\displaystyle \left(\genfrac{}{}{0px}{}{n}{1}\right)},\dots ,{\displaystyle \left(\genfrac{}{}{0px}{}{n}{n}\right)}$. Chaque ligne commence et finit par $1$ (valeurs particulières), et chaque nombre intérieur est la somme des deux nombres situés au-dessus de lui — celui juste au-dessus et celui au-dessus à gauche : c'est exactement la relation de Pascal. Voici les lignes $0$ à $6$ du triangle de Pascal :

On y lit par exemple ${\displaystyle \left(\genfrac{}{}{0px}{}{5}{2}\right)}=10$ : c'est la somme de ${\displaystyle \left(\genfrac{}{}{0px}{}{4}{2}\right)}=6$ et ${\displaystyle \left(\genfrac{}{}{0px}{}{4}{1}\right)}=4$, les deux nombres au-dessus. On y observe aussi la symétrie de chaque ligne (${\displaystyle \left(\genfrac{}{}{0px}{}{6}{2}\right)}={\displaystyle \left(\genfrac{}{}{0px}{}{6}{4}\right)}=15$) — c'est la propriété de symétrie démontrée plus haut. Une dernière observation saute aux yeux : les sommes des lignes valent $1$, $2$, $4$, $8$, $16$, $32$, $64$… les puissances de $2$. Ce n'est pas une coïncidence.

Démonstration (exigible) — par dénombrement. Comptons de deux façons les parties d'un ensemble $E$ à $n$ éléments. D'une part, nous avons démontré qu'il y en a $2^n$ en tout. D'autre part, classons-les selon leur cardinal : pour chaque entier $k$ compris entre $0$ et $n$, notons ${\mathcal{P}}_k$ l'ensemble des parties de $E$ ayant exactement $k$ éléments. Toute partie de $E$ a un cardinal bien défini, compris entre $0$ et $n$ : les ensembles ${\mathcal{P}}_0,{\mathcal{P}}_1,\dots ,{\mathcal{P}}_n$ sont donc deux à deux disjoints et leur réunion est l'ensemble de toutes les parties de $E$. Or $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{P}}_k)={\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}$ par définition des coefficients binomiaux. Le principe additif donne alors

$$\left(\genfrac{}{}{0px}{}{n}{0}\right)+\left(\genfrac{}{}{0px}{}{n}{1}\right)+\cdots +\left(\genfrac{}{}{0px}{}{n}{n}\right)=2^n\mathrm{.}\mathrm{\square }$$

Choisir le bon modèle

Toute la difficulté pratique du chapitre tient en une question : devant un énoncé concret, quel modèle appliquer ? Trois formules se disputent la place, et le choix se joue sur deux questions simples.

Un algorithme : construire une ligne du triangle de Pascal

La relation de Pascal est une définition de proche en proche : elle se traduit naturellement en un algorithme. Le programme suivant calcule la ligne $n$ du triangle en construisant chaque ligne à partir de la précédente : les extrémités valent $1$, et chaque terme intérieur est la somme de deux termes de la ligne du dessus.

def ligne_pascal(n):
    ligne = [1]                      # ligne 0 du triangle
    for i in range(1, n + 1):        # on construit les lignes 1, 2, ..., n
        nouvelle = [1]               # chaque ligne commence par 1
        for k in range(1, i):
            # relation de Pascal : C(i, k) = C(i-1, k-1) + C(i-1, k)
            nouvelle.append(ligne[k - 1] + ligne[k])
        nouvelle.append(1)           # chaque ligne se termine par 1
        ligne = nouvelle
    return ligne

print(ligne_pascal(6))   # affiche [1, 6, 15, 20, 15, 6, 1]

L'appel ligne_pascal(6) renvoie bien la ligne $6$ lue dans le tableau plus haut. Cet algorithme n'utilise que des additions d'entiers : aucune factorielle géante n'est calculée, ce qui le rend rapide et exact même pour de grandes valeurs de $n$ — on peut vérifier que sum(ligne_pascal(20)) vaut $2^{20}=1048576$, conformément à la dernière propriété.

En résumé : ce chapitre a bâti, à partir de deux principes évidents — on additionne les paquets disjoints, on multiplie les choix successifs — toute une arithmétique du comptage. Les $k$-uplets ($n^k$) modélisent les tirages avec remise, les $k$-uplets d'éléments distincts ($n(n-1)\cdots (n-k+1)$) les tirages sans remise où l'ordre compte, et les combinaisons ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}$ les choix où seul le groupe importe ; le nombre $2^n$ compte à la fois les parties d'un ensemble, les mots binaires et les chemins d'un arbre, et le triangle de Pascal organise tous les coefficients binomiaux autour d'une unique relation. Ces outils sont exactement ceux qu'attendait le calcul des probabilités depuis Pascal et Fermat : plus loin dans l'année, les coefficients binomiaux compteront les chemins d'un arbre de Bernoulli menant à $k$ succès en $n$ épreuves — et le dénombrement de ce chapitre deviendra la clé de la loi binomiale.