COMBINATOIRE ANALYSE

Construction de correspondances

Dans la première partie, nous avons passé en revue tous les ensembles finis qu'il était aisé de dénombrer en faisant usage des deux règles de la somme et du produit. Ces techniques élémentaires s'appliquent plus difficilement lorsqu'on veut dénombrer d'autres structures finies plus élaborées comme celles des arbres ou certains types de graphes. Le plus souvent on est conduit à chercher une correspondance biunivoque entre ces structures et les ensembles finis considérés dans la première partie. Jusqu'ici, il n'existe pas de théorie pour construire ces correspondances, tout est une question d'ingéniosité et de patience. À titre d'exemple, on peut décrire ci-dessous une telle correspondance entre les arbres de n sommets et les (n − 2)-uples (x₁, x₂, ..., x_n-2), où les x_i sont des entiers compris entre 1 et n.

Un graphe est la donnée d'un ensemble X – ses éléments sont les sommets du graphe – et d'une classe U de sous-ensembles de X à deux éléments, appelés arêtes. Si l'on a x, y ∈ X et {x, y} ∈ U, on dit que x et y sont adjacents. Une chaîne du graphe {X, U} est une suite {x₁, y₁}, {x₂, y₂}, ..., {x_n, y_n} d'arêtes distinctes telle que, lorsque n > 1, on ait :

pour i = 1, 2, ..., n − 1. Si de plus, on a n > 1 eton dit que la chaîne est un cycle. Un graphe est dit connexe si, pour tout couple de sommets distincts (x, y), il existe une chaîne {x₁, y₁}, {x₂, y₂}, ..., {x_n, y_n} telle que x₁ = x et y_n = y. Un arbre de n sommets est alors défini comme un graphe de n sommets qui est connexe et sans cycles. On a l'habitude de représenter un graphe fini de n sommets comme un ensemble de n points du plan numérotés de 1 à n où les sommets i et j sont reliés entre eux si et seulement si l'on a {i, j} ∈ U. Considérons par exemple le graphe de la figure ci-dessus. C'est un arbre de sept sommets, numérotés de 1 à 7.

Soit A_n l'ensemble de tous les arbres possibles de n sommets numérotés 1, 2, ..., n. Cayley fut le premier à démontrer que l'on a |A_n| = n^n-2. Or ce nombre est précisément le cardinal de l'ensemble H_n de tous les (n − 2)-uples (x₁, x₂, ..., x_n-2) où les x_i sont pris dans X = {1, 2, ..., n} (formule (11) de la première partie). Pour démontrer la formule |A_n| = n^n-2, il suffit donc de construire une bijection Φ de A_n sur H_n. Nous donnons ici la construction d'une telle correspondance due à Prüfer. Celle-ci fait usage des deux propriétés suivantes sur les arbres, faciles à vérifier. D'abord, un arbre a toujours (au moins) un sommet pendant, c'est-à-dire un sommet qui n'est adjacent qu'à un seul autre sommet. Ensuite, si l'on « efface » un sommet pendant d'un arbre de n sommets, et l'arête qui le contient, on obtient un arbre de (n − 1) sommets. La construction de Prüfer est alors la suivante : pour un arbre de A_n donné, on efface le plus petit sommet pendant et l'on désigne par x₁ l'unique sommet qui était adjacent à ce sommet pendant. On répète cette opération avec l'arbre restant de (n − 1) sommets et l'on détermine x₂ et ainsi de suite. On s'arrête lorsqu'il ne reste plus que deux sommets (adjacents). Par exemple, à l'arbre de la figure on fait correspondre la suite (1, 7, 1, 7, 7). Les sommets pendants qu'on a successivement effacés sont 2, 3, 4, 1, 5 et il est resté l'arbre formé par les deux sommets 6 et 7. On vérifie que l'application Φ de A_n sur H_n ainsi construite est bien bijective. D'où l'on déduit |A_n| = |H_n| = n^n-2.