Théorie > Combinatoire > Double comptage

Prérequis

Résumé

Ce chapitre présente la méthode du double comptage, qui permet de démontrer des résultats théoriques comme la formule de Cayley mais qui se révèle surtout être un outil très puissant pour démontrer des problèmes de combinatoire de haut niveau.

Ce chapitre a été écrit par N. Radu et mis en ligne le 28 février 2015.

1. 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.

2. Formule de Cayley

La technique du double comptage permet par exemple de prouver la formule de Cayley.

Pour expliquer ce à quoi cette formule s'intéresse, nous devons d'abord définir la notion d'arbre. Par définition, un arbre est un graphe (non-orienté) connexe qui ne contient aucun cycle. Un exemple d'arbre est donné ci-dessous.


Une propriété fondamentale d'un arbre est que son nombre d'arêtes est exactement égal à son nombre de sommets moins un. L'idée est que, si l'on est en présence de $n$ sommets, alors il faut au minimum $n-1$ arêtes pour être connexe; mais si on prend plus de $n-1$ arêtes, alors on créera un cycle. Pour avoir un arbre, il faut donc exactement $n-1$ arêtes. Une autre façon de le justifier est d'utiliser la formule d'Euler $s-a+f = 2$. En effet, comme un arbre ne possède pas de cycle, des arêtes ne délimitent jamais aucune zone du plan et le nombre de faces $f$ est donc toujours égal à $1$. On en déduit que $a = s-1$.

Maintenant que la notion d'arbre a été expliquée, nous pouvons nous demander, étant donné $n$ sommets, combien d'arbres distincts il est possible de créer à partir de ces $n$ sommets. On sait qu'il faut relier ces sommets avec $n-1$ arêtes, mais il y a bien sûr plusieurs manières de placer ces arêtes. La formule de Cayley est la réponse à cette question, que nous reformulons ci-dessous.

Problème
Quel est le nombre $T_n$ d'arbres différents que l'on peut construire sur $n$ sommets numérotés (pour $n > 1$) ?

On voit directement que $T_2 = 1$ et $T_3 = 3$ (voir schémas suivants), mais c'est déjà plus fastidieux de calculer $T_4$.


Il ne semble pas évident de trouver une formule pour $T_n$ en utilisant les méthodes classiques présentées. En effet, on peut par exemple essayer de placer les arêtes une par une et de compter le nombre de possibilités à chaque placement, mais ce nombre dépendra toujours des choix faits précédemment, ce qui rend le calcul impossible.

Une façon de calculer $T_n$ (il existe d'autres manières de le faire mais elles sont réputées moins élégantes) est d'utiliser le double comptage. La quantité que nous allons évaluer à deux reprises est le nombre de façons d'ajouter $n-1$ arêtes orientées (l'ordre des ajouts ayant de l'importance) à $n$ sommets initialement disjoints pour obtenir un arbre enraciné orienté. Par définition, un arbre enraciné orienté est un arbre où un sommet est privilégié (on l'appelle la racine de l'arbre) et où les arêtes sont toutes orientées dans la direction opposée à la racine. Un exemple d'arbre enraciné orienté est donné sur la figure suivante : la racine est le sommet numéroté $1$.


Nous pouvons calculer cette quantité de deux façons différentes :

  1. Pour la première méthode, on suppose connaître la valeur de $T_n$. On connaît donc le nombre d'arbres (non enracinés et non orientés) qu'on peut construire sur $n$ sommets. Pour chacun de ses $T_n$ arbres, il y a $n$ choix possibles de racines. Le choix de la racine détermine par ailleurs directement l'orientation que les arêtes de l'arbre doivent avoir. On a donc exactement $n \cdot T_n$ arbres enracinés orientés, et il reste à voir pour chacun le nombre de façons d'ajouter les $n-1$ arêtes une par une pour obtenir l'arbre. Clairement, cela revient simplement à choisir l'ordre dans lequel on ajoute les arêtes, et il y a $(n-1)!$ tels ordres. Au total, on en déduit que le nombre de façons d'ajouter $n-1$ arêtes orientées à $n$ sommets pour obtenir un arbre enraciné orienté est égal à
    $$n \cdot T_n \cdot (n-1)! = n! \cdot T_n.$$

  2. Pour la deuxième méthode, on adopte une approche classique : on va ajouter les arêtes une par une et voir, à chaque étape, combien il y a de choix possibles. Au départ, il y a $n$ sommets disjoints, qu'on peut voir comme étant $n$ arbres enracinés orientés triviaux (chaque arbre est constitué d'un seul sommet : sa racine). À chaque fois que l'on va ajouter une arête à notre graphe, on va relier deux arbres enracinés orientés existants pour qu'ils ne forment qu'un seul arbre enraciné orienté. Pour ce faire, il faut que l'arête que l'on ajoute aille d'un sommet quelconque de l'un des arbres à la racine d'un autre arbre. De cette façon, après la $k$-ème arête on sera en présence de $n-k$ arbres enracinés orientés. À la fin du processus, on aura donc $n-(n-1) = 1$ arbre enraciné orienté comme voulu. Il faut noter que cette façon de procéder (ajouter à chaque fois une arête d'un sommet quelconque d'un arbre vers la racine d'un autre arbre) est la seule manière qui permette d'obtenir un arbre enraciné orienté valide à la fin. En effet, si on ajoutait une autre arête, alors on aurait soit plus un arbre soit une orientation contradictoire.
    Il reste maintenant à évaluer le nombre de façons de suivre ce processus. Si $k-1$ arêtes ont déjà été placées, on est en présence de $n-k+1$ arbres et on désire rajouter la $k$-ème arête. Nous avons $n$ choix pour l'origine de cette arête comme on peut choisir n'importe quel sommet. Par contre, le point d'arrivée de cette arête doit être une racine d'un arbre autre que l'arbre contenant le point d'origine choisi : il y a donc $n-k$ choix pour celle-ci. Au total, on a donc $n\cdot(n-k)$ choix à la $k$-ème étape, d'où on obtient
    $$(n\cdot(n-1)) \cdot (n\cdot(n-2)) \cdot \ldots \cdot (n \cdot 2) \cdot (n \cdot 1) = n^{n-1} \cdot (n-1)! = n^{n-2} \cdot n!.$$

Nous avons donc prouvé que $n! \cdot T_n = n^{n-2}\cdot n!$, ce qui signifie que l'on a la formule suivante pour $T_n$.

Formule de Cayley
Le nombre d'arbres différents que l'on peut construire sur $n$ sommets numérotés $(n > 1)$ est
$$T_n = n^{n-2}.$$

Cette formule est intéressante en tant que telle, mais c'est surtout la méthode utilisée pour la prouver qui est digne d'intérêt.

3. Premier exemple

Certains problèmes de combinatoire, qui paraissent parfois très difficiles aux premiers abords, peuvent être résolus de manière très directe en utilisant le double comptage. Voici par exemple comment résoudre le problème suivant, qui n'est autre que le problème 2 de l'IMO 1998.

Problème (IMO 1998, P2)
Dans un concours, il y a $m$ participants et $n$ juges, où $n \geq 3$ est impair. Chaque participant est évalué par chaque juge comme ayant "réussi" ou "raté". Sachant que chaque paire de juges est d'accord sur au plus $k$ candidats, prouver que
$$\frac{k}{m} \geq \frac{n-1}{2n}.$$

Solution
Nous allons pour résoudre ce problème évaluer une quantité de deux manières différentes. Au vu des hypothèses, il n'est pas insensé de penser à dénombrer les couples $(\{J_1, J_2\}, P)$ où $J_1$ et $J_2$ sont des juges, $P$ est un participant et $J_1$ et $J_2$ sont d'accord sur $P$. Évaluons ce nombre $N$ de deux manières :

  1. Premièrement, regardons les paires de juges une par une. Il y a $C^2_n$ paires de juges $\{J_1,J_2\}$, et pour chacune de ces paires on sait par hypothèse qu'il existe au maximum $k$ participants $P$ tels que $J_1$ et $J_2$ sont d'accord sur $P$. Cela signifie que
    $$N \leq \frac{n(n-1)}{2} \cdot k.$$
  2. Considérons maintenant les participants un par un. Pour chaque participant $P$, notons $x$ le nombre de juges ayant noté $P$ comme "réussi". Il y a alors $n-x$ juges ayant noté $P$ comme "raté". Dans ce cas, le nombre de paires de juges étant d'accord sur $P$ est égal à
    $$C^2_x + C^2_{n-x} = \frac{x(x-1)}{2} + \frac{(n-x)\cdot(n-x-1)}{2} = \frac{2x^2-2nx+n^2-n}{2}.$$

  3. Le minimum de cette fonction en $x$ est atteint en $x = \frac{n}{2}$, mais comme $n$ est impair le minimum possible dans notre contexte est atteint en $x =\frac{n-1}{2}$ et $x = \frac{n+1}{2}$ ce qui donne
    $$\left(\frac{n-1}{2}\right)^2-n\left(\frac{n-1}{2}\right) + \frac{n^2-n}{2} = \left(\frac{n-1}{2}\right)^2.$$ On a donc au moins $\left(\frac{n-1}{2}\right)^2$ paires de juges pour chaque participant, ce qui donne finalement
    $$N \geq m \cdot \left(\frac{n-1}{2}\right)^2.$$
On a donc prouvé que
$$k \cdot \frac{n(n-1)}{2} \geq N \geq m \cdot \left(\frac{n-1}{2}\right)^2,$$ ce qui se révèle être équivalent à
$$\frac{k}{m} \geq \frac{n-1}{2n}.$$

4. Deuxième exemple

Voici un autre problème, d'un genre fort différent, qui peut également être résolu de cette manière. Il s'agit du problème 3 de l'IMO 1989.

Problème (IMO 1989, P3)
Soient $n$ et $k$ des entiers strictement positifs et $S$ un ensemble de $n$ points dans le plan tels que :
  1. Trois points distincts ne sont jamais alignés.
  2. Pour tout point $P$ de $S$, il y a au moins $k$ points de $S$ à égale distance de $P$.
Prouver que $$k < \frac{1}{2} + \sqrt{2n}.$$

Solution
Nous allons cette fois compter le nombre $N$ de couples $(P_1, \{P_2, P_3\})$ telles que $|P_1P_2| = |P_1P_3|$.

  1. Si on se fixe d'abord un point $P_1$, alors par hypothèse il y a au moins $k$ points à égale distance de $P_1$. On en déduit qu'il y a au moins $C^2_k$ paires de points $\{P_2, P_3\}$ telles que $|P_1P_2| = |P_1P_3|$. Puisqu'il y a $n$ choix pour $P_1$, on a
    $$N \geq n \cdot \frac{k(k-1)}{2}.$$
  2. Si maintenant, on se fixe d'abord deux points $P_2$ et $P_3$ distincts, alors un point $P_1$ se situe à égale distance de ces deux points si et seulement si $P_1$ est sur la médiatrice de $[P_2P_3]$. Comme il n'y a pas trois points alignés dans $S$, il y a au maximum $2$ points sur cette médiatrice, ce qui signifie qu'il y a au plus deux points $P_1$ tels que $|P_1P_2| = |P_1P_3|$. Puisqu'il y a $C^2_n$ façons de choisir $P_2$ et $P_3$, on a
    $$N \leq \frac{n(n-1)}{2} \cdot 2.$$
On a donc prouvé que
$$n \cdot \frac{k(k-1)}{2} \leq N \leq \frac{n(n-1)}{2} \cdot 2,$$ ce qui après simplification devient
$$k^2-k-2(n-1) \leq 0.$$ Le membre de gauche est un polynôme du second degré en $k$, et $k$ doit donc se situer entre les deux racines du polynôme pour que cette expression soit négative. Or, les deux racines sont données par
$$\frac{1 \pm \sqrt{1 + 8(n-1)}}{2},$$ donc on doit avoir
$$k \leq \frac{1 + \sqrt{8n-7}}{2} < \frac{1}{2} + \frac{\sqrt{8n}}{2} = \frac{1}{2} + \sqrt{2n},$$ ce qui est exactement la borne désirée pour $k$.