Théorie > Combinatoire > Double comptage

Principe

Le double comptage, aussi appelé double dénombrement, est une technique qui consiste à calculer une quantité combinatoire de deux manières différentes. Cette méthode permet de prouver des formules combinatoires, mais aussi de résoudre des problèmes d'olympiades a priori très difficiles.

Pour illustrer cette technique, nous allons d'abord examiner un exemple assez simple. Considérons le problème suivant, déjà rencontré précédemment :

Problème
Quel est le nombre de sous-ensembles (éventuellement vides) de $\{1, 2, \ldots, n\}$ ?

Il y a deux façons de résoudre ce problème :

  1. Pour construire un sous-ensemble $E \subseteq \{1, 2, \ldots, n\}$, on peut simplement décider pour chaque élément $i$ entre $1$ et $n$ si on le met dans $E$ ou non. On a donc deux choix pour l'élément $1$, deux choix pour $2$, ... et deux choix pour $n$. On a donc au total $2^n$ sous-ensembles.

  2. On peut décider de d'abord compter les sous-ensembles de $\{1, 2, \ldots, n\}$ ayant $0$ élément, puis ceux ayant $1$ élément, ... jusque ceux ayant $n$ éléments. Pour construire un sous-ensemble $E \subseteq \{1, 2, \ldots, n\}$ ayant exactement $k$ éléments, on doit simplement choisir ces $k$ éléments et on a dès lors $C^k_n$ tels sous-ensembles. Au total, on a donc $C^0_n + C^1_n + \ldots + C^{n-1}_n + C^n_n$ sous-ensembles.

Nous avons résolu le problème de deux manières et trouvé deux expressions différentes. Puisque nos deux manières de procéder sont correctes, on en déduit que les deux expressions obtenues sont identiques, et nous venons dès lors de prouver la formule
$$C^0_n + C^1_n + \ldots + C^{n-1}_n + C^n_n = 2^n,$$ que nous avions déjà prouvée à l'aide de la formule de Newton.