Double comptage

Définition intuitive

Un double comptage est une manière de trouver de jolies relations en combinatoire, simplement par le fait de comprendre un problème sous deux angles différents, et donc de dénombrer un ensemble de deux façons différentes.

Définition formelle

Pour rédiger un double comptage, on peut simplement comprendre un ensemble de deux manières différentes.
Une autre méthode répandue est de partir d’un couple d’éléments $(x,A)$ qui vérifie une certaine propriété $\mathcal{P}$. Ensuite on se demande combien peut-on choisir de $x$, puis combien de $A$ existent tels que $(x,A)$ vérifie $\mathcal{P}$. On raisonne aussi dans l’autre sens : on compte le nombre de $A$ possibles puis le nombre de $x$ qui vérifient que $(x,A)$ satisfait $\mathcal{P}$.

Exemple de rédaction

Considérons l’ensemble des couples $(x,A)$ où $x$ est un entier compris entre $1$ et $n$ et $A$ est une partie de $[\![1,n]\!]$ contenant $k$ éléments, dont $x$, et essayer de voir cet ensemble de deux manières différentes.

• D’un côté, on peut ainsi fixer $A$, il y a ainsi $\displaystyle\binom{n}{k}$ telles parties, où $\displaystyle \binom{n}{k}$ est le coefficient binomial "$k$ parmi $n$" du triangle de Pascal. Puis $A$ possède $k$ éléments donc on a $k$ possibilités pour $x$ tel que $(x,A)$ vérifie notre condition. Cela nous donne donc $\displaystyle k\binom{n}{k}$ d’un côté.

• De l’autre côté, on peut fixer $x$, il y a donc $n$ possibilités. Puis, pour construire $A$, on a déjà $x$, il nous reste plus qu’à prendre $k-1$ éléments de $[\![1,n]\!] \backslash \{x\}$ (ensemble à $n-1$ éléments), il y a alors $\displaystyle\binom{n-1}{k-1}$ telles parties. Cela nous donne donc $\displaystyle n\binom{n-1}{k-1}$.

Finalement on trouve la relation
$$\displaystyle k\binom{n}{k}=\displaystyle n\binom{n-1}{k-1}$$en égalisant nos deux comptages !

Bien sûr, on pourrait se dire que cette relation se déduit d’un simple calcul. Ceci dit, la combinatoire a surtout pour but de mieux comprendre le sens des objets, et ainsi cela permet de généraliser plus facilement qu’en trouvant des méthodes calculatoires qui marcheront uniquement pour chaque cas isolé.