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 »[1].
Cas particulier : dénombrement d'une partie d'un produit cartésien
[modifier | modifier le code]Principe
[modifier | modifier le code]Soient deux ensembles finis et , et une partie de ; chaque fois que appartient à , on dit que et sont incidents.
Notons que peut être vu comme le graphe d'une relation binaire de vers , auquel cas « et incidents » s'écrit , ou encore comme un graphe biparti.
Si désigne le nombre d'éléments incidents à , et celui des éléments incidents à , on a alors la formule dite du double décompte, ou du comptage par tranches (ou par piles) [2]:
.
Un cas particulier intéressant est celui où et sont constants ; la formule s'écrit alors .
Illustration par diagramme sagittal
[modifier | modifier le code]![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/3/39/Graphebi.gif/220px-Graphebi.gif)
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
[modifier | modifier le code]Si on définit la matrice d'incidence du graphe ou de la relation par si appartient à , sinon, la formule du double décompte signifie que la somme des termes de la matrice s'obtient soit en sommant lignes par lignes, soit en sommant colonnes par colonnes. En effet est le nombre de situés dans la ligne associée à , et est le nombre de situés dans la colonne associée à .
Dans l'exemple ci-contre, la matrice d'incidence est .
En ce sens, la formule du double décompte est un cas particulier de la formule d'interversion de signes de sommation : .
Exemples d'applications
[modifier | modifier le code]Somme des n premiers entiers
[modifier | modifier le code]Ici, les ensembles et sont égaux à l'ensemble des entiers de 1 à , et deux entiers et sont incidents si .
Alors et
La formule du double décompte s'écrit alors , dont on déduit la formule classique .
Nombre moyen de diviseurs [3]
[modifier | modifier le code]![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/6/60/Nbdiviseurs.gif/300px-Nbdiviseurs.gif)
Mêmes ensembles et , mais et sont incidents si divise .
Alors est le nombre de multiples de inférieurs ou égaux à , qui vaut où désigne la partie entière, et est le nombre des diviseurs de .
La formule du double décompte s'écrit alors ; on en déduit facilement que (série harmonique), et comme , on obtient que le nombre moyen de diviseurs d'un nombre entre 1 et équivaut à .
Somme des degrés des sommets d'un graphe
[modifier | modifier le code]Ici, l'ensemble est l'ensemble des sommets d'un graphe, 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'interprète comme le degré de , et pour une arête , ; la formule du double décompte s'écrit alors où 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é , où est le nombre de sommets.
De la même façon, dans un polyèdre où toutes les faces ont arêtes, où est le nombre de faces.
Formule sur les coefficients binomiaux
[modifier | modifier le code]Ici, l'ensemble est l'ensemble des parties à éléments d'un ensemble à éléments et l'ensemble des parties à éléments ; on décrète que deux parties et sont incidentes si elles sont disjointes.
Le nombre d'éléments du graphe vaut (choix de , puis choix de dans ). Or ici , qui est le nombre de disjoints de , vaut , et vaut . La formule du double décompte s'écrit alors :
.
Par exemple, en faisant , on obtient , ce qui, en changeant en donne l'importante formule du pion :
.
Autres exemples
[modifier | modifier le code]Somme d'une ligne du triangle de Pascal
[modifier | modifier le code]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 parties.
Deuxième méthode : le nombre d'éléments dans une partie est un entier entre 0 et . Le nombre de parties à éléments est le coefficient binomial , Ainsi, le nombre de parties est .
L'égalisation des deux expressions donne :
Petit théorème de Fermat
[modifier | modifier le code]![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/8/80/Proofs-of-Fermats-Little-Theorem-bracelet1.svg/220px-Proofs-of-Fermats-Little-Theorem-bracelet1.svg.png)
Le petit théorème de Fermat affirme que « si est un nombre premier et si est un entier quelconque, alors est un multiple de ». Par exemple :
- 43 - 4 = 60 qui est divisible par 3.
Soit un nombre premier et un nombre entier. Considérons un alphabet constitué de symboles. Comptons les mots de longueur dans lesquels il y a au moins deux symboles distincts.
Première méthode : il y a en tout mots de longueur dans l'alphabet, desquels il faut retirer les mots constitués d'un seul et même symbole :
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/0/08/Proofs-of-Fermats-Little-Theorem-bracelet2.svg/220px-Proofs-of-Fermats-Little-Theorem-bracelet2.svg.png)
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 et si l'on considère des mots de trois lettres, les trois mots , et sont dans le même collier.
Il y a mots de symboles dans chaque collier. En effet, chacune des permutations donne un mot différent, car est premier. Ce ne serait pas le cas si n'était pas premier, il n'y a par exemple que 2 mots différents de 4 symboles dans le collier . On a donc :
En écrivant l'égalité entre ces deux expressions pour , on trouve que est divisible par .
Dénombrement des arbres colorés
[modifier | modifier le code]![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/e/ee/Cayley%27s_formula_2-4.svg/220px-Cayley%27s_formula_2-4.svg.png)
Quel est le nombre d'arbres colorés différents qui peuvent recouvrir un ensemble de sommets distincts ? La formule de Cayley donne la réponse :
- .
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 »[4],[5].
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 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 façons de choisir la première arête, puis 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 :
- .
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/8/83/Graph.tree._Cayley%27s_formula.png/220px-Graph.tree._Cayley%27s_formula.png)
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 arêtes de façon à former une forêt de k arbres orientés (illustration), il y a 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 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 :
- .
En écrivant l'égalité entre ces deux expressions pour le nombre de suites d'arêtes,
- ,
on obtient la formule de Cayley :
- .
Autres exemples
[modifier | modifier le code]- 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
[modifier | modifier le code]- (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.
- (en) Jacobus H. van Lint et Richard M. Wilson, A Course in Combinatorics, Cambridge University Press, , 602 p. (ISBN 978-0-521-00601-9, lire en ligne), p. 4, p. 4 « One of the important tools in combinatorics is the method of counting certain objects in two different ways ».
- Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer-Verlag, , p. 186.
- Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer-Verlag, , p. 187.
- (en) Martin Aigner et Günter M. Ziegler, Proofs from THE BOOK, Springer-Verlag, , p. 145-146.
- Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer-Verlag, , p. 229-230.