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

Principe

modifier

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

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

Somme des n premiers entiers

modifier

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

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

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

Somme d'une ligne du triangle de Pascal

modifier

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

Notes et références

modifier
  • 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.