Voir la source de Preuve par double dénombrement

{{À sourcer|date=décembre 2019}}

En [[Combinatoire|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 »<ref>{{Ouvrage | langue=en | prénom1=Jacobus H. | nom1=van Lint | prénom2=Richard M. | nom2=Wilson | titre=A Course in Combinatorics | éditeur=[[Cambridge University Press]] | année=2001 | pages totales=602 | passage=4 | isbn=978-0-521-00601-9 | lire en ligne=https://books.google.com/books?id=5l5ps2JkyT0C&printsec=frontcover}}, p. 4 « ''One of the important tools in combinatorics is the method of counting certain objects in two different ways'' ».</ref>.

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

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

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

Si <math>n^+(x)</math> désigne le nombre d'éléments <math>y</math> incidents à <math>x</math>, et <math>n^-(y)</math> celui des éléments <math>x</math> incidents à <math>y</math>, on a alors la formule dite du ''double décompte'', ou du ''comptage par tranches'' (ou ''par piles)'' <ref>{{Ouvrage|langue=fr|prénom1=Martin|nom1=Aigner|prénom2=Günter M.|nom2=Ziegler|lien auteur2=Günter M. Ziegler|titre=[[Raisonnements divins]]|éditeur=[[Springer-Verlag]]|année=2013|passage=186|isbn=}}.</ref>:

<math>\sum_{x \in E}n^+(x)=\sum_{y \in F}n^-(y)=\left\vert \mathcal G \right\vert =\text{card }\mathcal G</math>.

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

=== Illustration par diagramme sagittal ===
[[Fichier:Graphebi.gif|vignette|La formule du double décompte s'écrit dans cet exemple : <math>1+2+2+1+2=3+2+1+2=8</math>]]
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]] <math>A</math> du graphe <math>\mathcal G</math> ou de la relation <math>R</math> par <math>A(x,y)=1</math> si <math>(x,y)</math> appartient à <math>\mathcal G</math>, <math>A(x,y)=0</math> sinon, la formule du double décompte signifie que la somme des termes de la matrice <math>A</math> s'obtient soit en sommant lignes par lignes, soit en sommant colonnes par colonnes. En effet <math>n^+(x)</math> est le nombre de <math>1</math> situés dans la ''ligne'' associée à <math>x</math>, et <math>n^-(y)</math> est le nombre de <math>1</math> situés dans la ''colonne'' associée à <math>y</math>.

Dans l'exemple ci-contre, la matrice d'incidence est <math>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}</math>.

En ce sens, la formule du double décompte est un cas particulier de la formule d'[[v:Sommation/Sommation_double|interversion de signes de sommation]] : <math>\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}</math>.

=== Exemples d'applications ===

==== Somme des {{Math|§=''n''}} premiers entiers ====
Ici, les ensembles <math>\mathcal E</math> et <math>\mathcal F</math> sont égaux à l'ensemble des entiers de 1 à <math>n</math>, et deux entiers <math>i</math> et <math>j</math> sont incidents si <math>i\leqslant j</math> .

Alors <math>n^+(i)=n+1-i</math>  et <math>n^-(i)=i</math>

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

==== Nombre moyen de diviseurs <ref>{{Ouvrage|langue=fr|prénom1=Martin|nom1=Aigner|prénom2=Günter M.|nom2=Ziegler|lien auteur2=Günter M. Ziegler|titre=[[Raisonnements divins]]|éditeur=[[Springer-Verlag]]|année=2013|passage=187|isbn=}}.</ref> ====
[[Fichier:Nbdiviseurs.gif|vignette|300x300px|Courbe du nombre moyen de diviseurs d'un nombre entre 1 et <math>n</math> avec, en rouge, la courbe de <math>\ln n</math>.|alt=]]
Mêmes ensembles <math>\mathcal E</math> et <math>\mathcal F</math> , mais <math>i</math> et <math>j</math> sont incidents si <math>i</math> ''divise'' <math>j</math>.

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

La formule du double décompte s'écrit alors <math>\sum_{i=1}^nd(i)=\sum_{i=1}^n\left \lfloor \frac{n}{i} \right \rfloor</math> ; on en déduit facilement que <math> {1\over n}\sum_{i=1}^nd(i)\sim\sum_{i=1}^n{1\over i}=H_n</math> ([[série harmonique]]), et comme <math>H_n\sim\ln n</math>, on obtient que le nombre moyen de diviseurs d'un nombre entre 1 et <math>n</math> équivaut à <math>\ln n</math>.

==== Somme des degrés des sommets d'un graphe ====
Ici, l'ensemble <math>\mathcal E</math> est l'ensemble des sommets d'un [[Graphe (mathématiques discrètes)|graphe]],  <math>\mathcal F</math> l'ensemble de ses arêtes, et la relation d'incidence celle d'adjacence entre les sommets et les arêtes. Pour un sommet <math>s</math>, <math>n^+(s)</math> s'interprète comme le degré de <math>s</math>, et pour une arête <math>a</math>, <math>n^-(a)=2</math> ; la formule du double décompte s'écrit alors <math>\sum\operatorname{deg}(s) = 2 A</math> où <math>A</math> 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é <math>n</math>, <math>nS=2A</math> où <math>S</math> est le nombre de sommets.

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

==== Formule sur les coefficients binomiaux ====
Ici, l'ensemble <math>\mathcal E</math> est l'ensemble des parties à <math>p</math> éléments d'un ensemble à <math>n</math> éléments et <math>\mathcal F</math> l'ensemble des parties à <math>q</math> éléments ; on décrète que deux parties <math>A</math> et <math>B</math> sont incidentes si elles sont ''disjointes''.

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

<math>\binom{n}{p}\binom{n-p}{q}=\binom{n}{q}\binom{n-q}{p}=\binom{n}{p+q}\binom{p+q}{p}</math>.

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

<math>\binom{n}{p}={n \over p}\binom{n-1}{p-1}</math>.

<br />

== 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 <math>2 \times 2 \times \ldots \times 2 \, (n\mbox{ fois}), soit 2^n</math> parties.

'''Deuxième méthode''' : le nombre d'éléments dans une partie est un entier <math>p</math> entre 0 et <math>n</math>. Le nombre de parties  à <math>p</math> éléments est le [[coefficient binomial]] <math>\binom{n}{p}</math>, Ainsi, le nombre de parties est <math>\sum_{p=0}^n \binom{n}{p}</math>.

L'égalisation des deux expressions donne :
:<math>\sum_{p=0}^n \binom{n}{p} = 2^n</math>

=== Petit théorème de Fermat ===
[[Fichier:Proofs-of-Fermats-Little-Theorem-bracelet1.svg|thumb|left|Collier représentant 7 mots différents.]]
Le [[petit théorème de Fermat]] affirme que « si <math>p</math> est un [[nombre premier]] et si <math>a</math> est un entier quelconque, alors <math>a^p-a</math> est un multiple de <math>p</math> ». Par exemple :

: 4<sup>3</sup> - 4 = 60 qui est divisible par 3.

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

'''Première méthode''' : il y a en tout <math>a^p</math> mots de longueur <math>p</math> dans l'alphabet, desquels il faut retirer les <math>a</math> mots constitués d'un seul et même symbole :
:<math>n = a^p - a</math>

[[Fichier:Proofs-of-Fermats-Little-Theorem-bracelet2.svg|thumb|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 [[Collier (combinatoire)|colliers]] ''(illustration)''. Par exemple, si l'alphabet est <math>\{A, B, C, D\}</math> et si l'on considère des mots de trois lettres, les trois mots <math>ABD</math>, <math>BDA</math> et <math>DAB</math> sont dans le même collier.

Il y a <math>p</math> mots de <math>p</math> symboles dans chaque collier. En effet, chacune des <math>p</math> permutations donne un mot différent, car <math>p</math> est premier. Ce ne serait pas le cas si <math>p</math> n'était pas premier, il n'y a par exemple que 2 mots différents de 4 symboles dans le collier <math>ABAB</math>. On a donc :
:<math>n = p .\text{(nombre de colliers)}</math>

En écrivant l'égalité entre ces deux expressions pour <math>n</math>, on trouve que ''<math>n = a^p - a</math>'' est divisible par <math>p</math>.

=== Dénombrement des arbres colorés ===
[[Fichier:Cayley's formula 2-4.svg|thumb|left|La [[formule de Cayley]] indique qu'il y a {{nobr|1 {{=}} 2<sup>2 − 2</sup>}} arbre à deux sommets, {{nobr|3 {{=}} 3<sup>3 − 2</sup>}} arbres colorés à trois sommets et {{nobr|16 {{=}} 4<sup>4 − 2</sup>}} arbres colorés à 4 sommets.]]
Quel est le nombre <math>C_n</math> d'[[Arbre (graphe)|arbres]] colorés différents qui peuvent recouvrir un ensemble de <math>n</math> sommets distincts ? La [[formule de Cayley]] donne la réponse :

:<math>C_n = n^{n-2}</math>.

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 {{Citation|la plus belle d'entre elles}}<ref>{{Ouvrage|langue=en|prénom1=Martin|nom1=Aigner|prénom2=Günter M.|nom2=Ziegler|lien auteur2=Günter M. Ziegler|titre=[[Proofs from THE BOOK]]|éditeur=[[Springer-Verlag]]|année=1998|passage=145-146|isbn=}}.</ref>{{,}}<ref>{{Ouvrage|langue=fr|prénom1=Martin|nom1=Aigner|prénom2=Günter M.|nom2=Ziegler|lien auteur2=Günter M. Ziegler|titre=[[Raisonnements divins]]|éditeur=[[Springer-Verlag]]|année=2013|passage=229-230|isbn=}}.</ref>.

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 <math>C_n</math> 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 <math>n-1</math> façons de choisir la première arête, puis <math>n-2</math> 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 :

:<math>C_n n!</math>.

[[Fichier:Graph.tree. Cayley's formula.png|thumb|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 <math>n-k</math> arêtes de façon à former une forêt de ''k'' arbres orientés ''(illustration)'', il y a <math>n(k-1)</math> 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 <math>k-1</math> 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 :

:<math>\prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!</math>.

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

:<math>C_n n!=n^{n-2}n!</math>,

on obtient la formule de Cayley :

:<math>C_n=n^{n-2}</math>.
=== Autres exemples ===
* L'[[identité de Vandermonde]], l'[[Théorème de l'étoile de David#Énoncé 2|identité de l'étoile de David]], autres propriétés des [[Coefficient binomial|coefficients binomiaux]] qui peuvent être démontrées par double dénombrement.
* Les [[Nombre pyramidal carré|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 (géométrie)|réseau]] dans un triangle.

== Notes et références ==
{{Traduction/Référence|en|Double counting (proof technique)|520464770}}
{{Crédit d'auteurs|interne|Preuve bijective|86669611}}, où l'on compte séparément deux ensembles liés par une bijection pour établir l'égalité entre deux quantités.
{{Références}}

{{Portail|mathématiques}}

[[Catégorie:Combinatoire]]
[[Catégorie:Raisonnement mathématique]]