Preuve par double dénombrement

En mathématiques combinatoires, une preuve par double dénombrement, ou double comptage, ou encore double décompte, est une technique de preuve combinatoire servant à démontrer que deux expressions sont égales en prouvant qu'il y a deux façons de compter le nombre d'éléments d'un même ensemble. Van Lint et Wilson décrivent cette technique comme « un des outils les plus importants en combinatoire ».

Cas particulier : dénombrement d'une partie d'un produit cartésien

Principe

Soient deux ensembles finis ${\mathcal {E}}$ et ${\mathcal {F}}$, et une partie ${\mathcal {G}}$ de ${\mathcal {E}}\times {\mathcal {F}}$ ; chaque fois que $(x,y)$ appartient à ${\mathcal {G}}$, on dit que $x$ et $y$ sont incidents.

Notons que ${\mathcal {G}}$ peut être vu comme le graphe d'une relation binaire $R$ de ${\mathcal {E}}$ vers ${\mathcal {F}}$, auquel cas « $x$ et $y$ incidents » s'écrit $xRy$, ou encore comme un graphe biparti.

Si $n^{+}(x)$ désigne le nombre d'éléments $y$ incidents à $x$, et $n^{-}(y)$ celui des éléments $x$ incidents à $y$, on a alors la formule dite du double décompte, ou du comptage par tranches (ou par piles) :

$\sum _{x\in E}n^{+}(x)=\sum _{y\in F}n^{-}(y)=\left\vert {\mathcal {G}}\right\vert ={\text{card }}{\mathcal {G}}$.

Un cas particulier intéressant est celui où $n^{+}$ et $n^{-}$ sont constants ; la formule s'écrit alors $n^{+}\cdot \left\vert {\mathcal {E}}\right\vert =n^{-}\cdot \left\vert {\mathcal {F}}\right\vert$.

Illustration par diagramme sagittal

La formule du double décompte s'écrit dans cet exemple : $1+2+2+1+2=3+2+1+2=8$

La formule du double décompte s'interprète dans ce diagramme par le fait que le nombre de flèches est égal au nombre de leurs départs ainsi qu'au nombre de leurs arrivées.

Illustration par matrice d'incidence

Si on définit la matrice d'incidence $A$ du graphe ${\mathcal {G}}$ ou de la relation $R$ par $A(x,y)=1$ si $(x,y)$ appartient à ${\mathcal {G}}$, $A(x,y)=0$ sinon, la formule du double décompte signifie que la somme des termes de la matrice $A$ s'obtient soit en sommant lignes par lignes, soit en sommant colonnes par colonnes. En effet $n^{+}(x)$ est le nombre de $1$ situés dans la ligne associée à $x$, et $n^{-}(y)$ est le nombre de $1$ situés dans la colonne associée à $y$.

Dans l'exemple ci-contre, la matrice d'incidence est $A={\begin{pmatrix}&\alpha &\beta &\gamma &\delta \\a&1&0&0&0\\b&1&1&0&0\\c&0&0&1&1\\d&0&1&0&0\\e&1&0&0&1\end{pmatrix}}$.

En ce sens, la formule du double décompte est un cas particulier de la formule d'interversion de signes de sommation : $\sum _{(i,j)\in I\times J}a_{i,j}=\sum _{i\in I}\sum _{j\in J}a_{i,j}=\sum _{j\in J}\sum _{i\in I}a_{i,j}$.

Exemples d'applications

Somme des n premiers entiers

Ici, les ensembles ${\mathcal {E}}$ et ${\mathcal {F}}$ sont égaux à l'ensemble des entiers de 1 à $n$, et deux entiers $i$ et $j$ sont incidents si $i\leqslant j$ .

Alors $n^{+}(i)=n+1-i$ et $n^{-}(i)=i$

La formule du double décompte s'écrit alors $\sum _{i=1}^{n}(n+1-i)=\sum _{i=1}^{n}i$, dont on déduit la formule classique $\sum _{i=1}^{n}i={n(n+1) \over {2}}$.

Nombre moyen de diviseurs

Courbe du nombre moyen de diviseurs d'un nombre entre 1 et $n$ avec, en rouge, la courbe de $\ln n$.

Mêmes ensembles ${\mathcal {E}}$ et ${\mathcal {F}}$ , mais $i$ et $j$ sont incidents si $i$ divise $j$.

Alors $n^{+}(i)$ est le nombre de multiples de $i$ inférieurs ou égaux à $n$, qui vaut $\left\lfloor {\frac {n}{i}}\right\rfloor$ où $\left\lfloor .\right\rfloor$ désigne la partie entière, et $n^{-}(i)$ est le nombre $d(i)$ des diviseurs de $i$.

La formule du double décompte s'écrit alors $\sum _{i=1}^{n}d(i)=\sum _{i=1}^{n}\left\lfloor {\frac {n}{i}}\right\rfloor$ ; on en déduit facilement que ${1 \over n}\sum _{i=1}^{n}d(i)\sim \sum _{i=1}^{n}{1 \over i}=H_{n}$ (série harmonique), et comme $H_{n}\sim \ln n$, on obtient que le nombre moyen de diviseurs d'un nombre entre 1 et $n$ équivaut à $\ln n$.

Somme des degrés des sommets d'un graphe

Ici, l'ensemble ${\mathcal {E}}$ est l'ensemble des sommets d'un graphe, ${\mathcal {F}}$ l'ensemble de ses arêtes, et la relation d'incidence celle d'adjacence entre les sommets et les arêtes. Pour un sommet $s$, $n^{+}(s)$ s'interprète comme le degré de $s$, et pour une arête $a$, $n^{-}(a)=2$ ; la formule du double décompte s'écrit alors $\sum \operatorname {deg} (s)=2A$ où $A$ est le nombre d'arêtes du graphe. On en déduit que le nombre de sommets de degré impair est pair, ce qui constitue le lemme des poignées de main.

On en déduit aussi par exemple que dans un polyèdre dont tous les sommets sont de degré $n$, $nS=2A$ où $S$ est le nombre de sommets.

De la même façon, dans un polyèdre où toutes les faces ont $p$ arêtes, $pF=2A$ où $F$ est le nombre de faces.

Formule sur les coefficients binomiaux

Ici, l'ensemble ${\mathcal {E}}$ est l'ensemble des parties à $p$ éléments d'un ensemble à $n$ éléments et ${\mathcal {F}}$ l'ensemble des parties à $q$ éléments ; on décrète que deux parties $A$ et $B$ sont incidentes si elles sont disjointes.

Le nombre d'éléments du graphe ${\mathcal {G}}$ vaut ${\binom {n}{p+q}}{\binom {p+q}{p}}$ (choix de $A\cup B$, puis choix de $A$ dans $A\cup B$). Or ici $n^{+}(A)$, qui est le nombre de $B$ disjoints de $A$, vaut ${\binom {n-p}{q}}$, et $n^{-}(B)$ vaut ${\binom {n-q}{p}}$. La formule du double décompte s'écrit alors :

${\binom {n}{p}}{\binom {n-p}{q}}={\binom {n}{q}}{\binom {n-q}{p}}={\binom {n}{p+q}}{\binom {p+q}{p}}$.

Par exemple, en faisant $q=1$, on obtient $(n-p){\binom {n}{p}}=n{\binom {n-1}{p}}=(p+1){\binom {n}{p+1}}$, ce qui, en changeant $p$ en $p-1$ donne l'importante formule du pion :

${\binom {n}{p}}={n \over p}{\binom {n-1}{p-1}}$.

Autres exemples

Somme d'une ligne du triangle de Pascal

Cherchons le nombre de parties d'un ensemble à n éléments.

Première méthode : il y a deux possibilités pour chaque élément : soit il est dans la partie, soit il n'y est pas. Par conséquent, il y a un total de $2\times 2\times \ldots \times 2\,(n{\mbox{ fois}}),soit2^{n}$ parties.

Deuxième méthode : le nombre d'éléments dans une partie est un entier $p$ entre 0 et $n$. Le nombre de parties à $p$ éléments est le coefficient binomial ${\binom {n}{p}}$, Ainsi, le nombre de parties est $\sum _{p=0}^{n}{\binom {n}{p}}$.

L'égalisation des deux expressions donne :

$\sum _{p=0}^{n}{\binom {n}{p}}=2^{n}$

Petit théorème de Fermat

Collier représentant 7 mots différents.

Le petit théorème de Fermat affirme que « si $p$ est un nombre premier et si $a$ est un entier quelconque, alors $a^{p}-a$ est un multiple de $p$ ». Par exemple :

4³ - 4 = 60 qui est divisible par 3.

Soit $p$ un nombre premier et $a$ un nombre entier. Considérons un alphabet constitué de $a$ symboles. Comptons les $n$ mots de longueur $p$ dans lesquels il y a au moins deux symboles distincts.

Première méthode : il y a en tout $a^{p}$ mots de longueur $p$ dans l'alphabet, desquels il faut retirer les $a$ mots constitués d'un seul et même symbole :

$n=a^{p}-a$

Collier ne représentant qu'un seul mot.

Deuxième méthode : ces mots peuvent être regroupés en ensembles de mots qui peuvent être déduits l'un de l'autre par permutation circulaire. On appelle ces ensembles des colliers (illustration). Par exemple, si l'alphabet est $\{A,B,C,D\}$ et si l'on considère des mots de trois lettres, les trois mots $ABD$, $BDA$ et $DAB$ sont dans le même collier.

Il y a $p$ mots de $p$ symboles dans chaque collier. En effet, chacune des $p$ permutations donne un mot différent, car $p$ est premier. Ce ne serait pas le cas si $p$ n'était pas premier, il n'y a par exemple que 2 mots différents de 4 symboles dans le collier $ABAB$. On a donc :

$n=p.{\text{(nombre de colliers)}}$

En écrivant l'égalité entre ces deux expressions pour $n$, on trouve que $n=a^{p}-a$ est divisible par $p$.

Dénombrement des arbres colorés

La formule de Cayley indique qu'il y a 1 = 2^{2 − 2} arbre à deux sommets, 3 = 3^{3 − 2} arbres colorés à trois sommets et 16 = 4^{4 − 2} arbres colorés à 4 sommets.

Quel est le nombre $C_{n}$ d'arbres colorés différents qui peuvent recouvrir un ensemble de $n$ sommets distincts ? La formule de Cayley donne la réponse :

$C_{n}=n^{n-2}$.

Aigner et Ziegler énumèrent quatre démonstrations différentes de ce résultat. Ils affirment que, des quatre, c'est la démonstration par double dénombrement que l'on doit à Jim Pitman qui est « la plus belle d'entre elles ».

Dans cette démonstration on dénombre de deux façons les différentes suites d'arêtes orientées qui peuvent être ajoutées à un graphe nul (sans arêtes) de n sommets pour former un arbre.

Première méthode : on part de l'un des $C_{n}$ arbres non orientés possibles et on choisit l'un de ses n sommets comme racine de l'arbre orienté, ce qui donne un arbre orienté. Il y a $n-1$ façons de choisir la première arête, puis $n-2$ façons de choisir l'arête suivante, et ainsi de suite. Finalement, le nombre total de suites qui peuvent être formées de cette façon est :

$C_{n}n!$.

Ajouter une arête orientée à une forêt orientée.

Deuxième méthode : on ajoute les arêtes une à une au graphe vide, en considérant le nombre de choix que l'on a à disposition à chaque étape. Si l'on a déjà ajouté une collection de $n-k$ arêtes de façon à former une forêt de k arbres orientés (illustration), il y a $n(k-1)$ choix pour la prochaine arête à ajouter. En effet, son sommet de départ peut être n'importe lequel des n sommets du graphe et son sommet d'arrivée peut être n'importe lequel des $k-1$ racines autres que la racine de l'arbre contenant le sommet de départ (illustration). Finalement, en multipliant le nombre de choix à la première étape, à la deuxième étape, etc., le nombre total de choix est :

$\prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!$.

En écrivant l'égalité entre ces deux expressions pour le nombre de suites d'arêtes,

$C_{n}n!=n^{n-2}n!$,

on obtient la formule de Cayley :

$C_{n}=n^{n-2}$.

Autres exemples

• L'identité de Vandermonde, l'identité de l'étoile de David, autres propriétés des coefficients binomiaux qui peuvent être démontrées par double dénombrement.
• Les nombres pyramidaux carrés. L'égalité entre la somme des n premiers carrés et un polynôme du troisième degré peut être démontrée par double dénombrement des triplets de nombres entiers (x, y, z) où z est plus grand que chacun des deux autres nombres.
• L'Inégalité de Lubell-Yamamoto-Meshalkin. La démonstration de D. Lubell de ce résultat sur les familles d'ensembles utilise un argument de double dénombrement sur des permutations pour prouver cette fois une inégalité plutôt qu'une égalité.
• La loi de réciprocité quadratique. Une démonstration due à Gotthold Eisenstein permet d'obtenir cet autre résultat important de la théorie des nombres, en comptant de deux façons différentes les points d'un réseau dans un triangle.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Double counting (proof technique) » (voir la liste des auteurs).

• Cet article est partiellement ou en totalité issu de l'article intitulé « Preuve bijective » (voir la liste des auteurs)., où l'on compte séparément deux ensembles liés par une bijection pour établir l'égalité entre deux quantités.