Aller au contenu

Preuve par double dénombrement

Un article de Wikipédia, l'encyclopédie libre.

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]

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]
La formule du double décompte s'écrit dans cet exemple :

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]
Courbe du nombre moyen de diviseurs d'un nombre entre 1 et avec, en rouge, la courbe de .

Mêmes ensembles et , mais et sont incidents si divise .

Alors est le nombre de multiples de inférieurs ou égaux à , qui vaut 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 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é , est le nombre de sommets.

De la même façon, dans un polyèdre où toutes les faces ont arêtes, 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]
Collier représentant 7 mots différents.

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 :

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 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]
La formule de Cayley indique qu'il y a 1 = 22 − 2 arbre à deux sommets, 3 = 33 − 2 arbres colorés à trois sommets et 16 = 44 − 2 arbres colorés à 4 sommets.

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 :

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

Notes et références

[modifier | modifier le code]
  • 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.
  1. (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 ».
  2. Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer-Verlag, , p. 186.
  3. Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer-Verlag, , p. 187.
  4. (en) Martin Aigner et Günter M. Ziegler, Proofs from THE BOOK, Springer-Verlag, , p. 145-146.
  5. Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer-Verlag, , p. 229-230.