formule de Cayley

Prenez quatre points portant les numéros 1, 2, 3 et 4. Il faut les relier pour que chacun puisse atteindre tous les autres, sans jamais former de boucle fermée. Une telle liaison est un arbre étiqueté.

La formule de Cayley évite de dessiner toutes les possibilités : elle en annonce 16. Les numéros comptent vraiment. Deux dessins de même forme peuvent représenter deux arbres distincts lorsque les numéros n'occupent pas les mêmes places.

Un arbre étiqueté est un graphe simple non orienté, connexe et sans cycle, dont chaque sommet porte une étiquette distincte. Les sommets forment un ensemble fixé de cardinal n, et l'ensemble de leurs n étiquettes est lui aussi fixé. Deux arbres sont distincts lorsque leurs ensembles d'arêtes ne sont pas les mêmes sur ces sommets étiquetés. Dans le cadre de cette formule, on parle aussi d'arbre de Cayley pour désigner un tel arbre étiqueté.

Pour n au moins égal à 2, la formule de Cayley donne le nombre total de ces arbres : $n^{n-2}n^\{n-2\}$. Elle fournit 1 arbre pour n = 2, 3 arbres pour n = 3 et 16 arbres pour n = 4. La forme non étiquetée ne suffit donc pas à déterminer ce qui est compté : il faut regarder quelles paires d'étiquettes sont reliées.

En 1860, Karl Borchardt a démontré par un calcul de déterminant un résultat équivalent à la formule. En 1889, Arthur Cayley l'a formulée en termes d'arbres et a donné un dénombrement plus fin tenant compte des degrés des sommets ; son nom s'est ensuite imposé. Une démonstration classique utilise le code de Prüfer, une bijection avec les suites de longueur n − 2 dont chaque terme appartient à l'ensemble des n étiquettes.

Soit un ensemble fixé de n étiquettes distinctes, avec n ≥ 2. Notons N_n le nombre d'arbres simples non orientés ayant exactement ces sommets. Alors :

Ici, N_n désigne le nombre recherché. Le code de Prüfer explique directement l'exposant : il associe à chaque arbre une unique suite de n − 2 positions, avec n choix possibles à chaque position.

La formule s'applique à un ensemble fixé de n sommets portant des étiquettes toutes distinctes. Les graphes comptés sont simples, non orientés, connexes et sans cycle. Ces deux dernières propriétés imposent qu'un arbre à n sommets possède n − 1 arêtes. Le résultat annoncé porte sur n ≥ 2.

Si les étiquettes sont oubliées, le calcul n'est plus nⁿ⁻² : il faut regrouper les arbres qui ne diffèrent que par le nom de leurs sommets. De même, un graphe déconnecté, un graphe contenant un cycle ou une boucle n'appartient pas à la famille comptée ; il faut alors employer un dénombrement adapté à cette autre famille.

Prenons les quatre sommets étiquetés 1, 2, 3 et 4. Un code de Prüfer a alors n − 2 = 2 termes. Choisissons la suite (2, 2) et reconstruisons son arbre.

1. Les occurrences du code donnent les degrés initiaux : le sommet 2 a le degré 3, tandis que 1, 3 et 4 ont chacun le degré 1.

2. La plus petite étiquette de degré 1 est 1. Relions 1 au premier terme du code, soit 2, puis retirons 1 et ce premier terme.

3. La plus petite étiquette disponible de degré 1 est maintenant 3. Relions 3 au second 2, puis retirons 3 et ce terme. Il reste les sommets 2 et 4, que l'on relie. Le graphe obtenu porte donc les arêtes 1–2, 2–3 et 2–4 ; la figure en montre la structure exacte.

4. Pour contrôler le total, chacune des deux positions du code accepte l'une des quatre étiquettes. Il existe donc 4 × 4 = 16 codes. La bijection de Prüfer garantit qu'ils donnent exactement les 16 arbres étiquetés annoncés par 4⁴⁻² = 16.

Pour compter des réseaux arborescents dont les n points sont nommés, vérifiez d'abord que chaque réseau relie tous les points sans cycle. La formule remplace alors une énumération dessin par dessin. Si les points ne sont pas distingués, il faut choisir un dénombrement d'arbres non étiquetés.

Pour construire systématiquement un arbre étiqueté, choisissez une suite de Prüfer de longueur n − 2, puis appliquez le décodage. Cette représentation est préférable au dessin lorsque l'on veut enregistrer, comparer ou générer les arbres sans en oublier.

Pour contrôler une liste obtenue autrement, comparez son nombre d'éléments à nⁿ⁻² et vérifiez qu'aucun ensemble d'arêtes n'est répété. L'accord sur le total ne suffit pas si la liste contient à la fois des doublons et des omissions.

Un arbre étiqueté ne se confond pas avec un arbre non étiqueté. Dans le premier, les sommets 1, 2, 3 et 4 sont distingués et les arêtes relient des étiquettes précises. Dans le second, seules les formes comptent : renommer les sommets ne crée pas un nouvel objet. Pour trancher, demandez si permuter deux noms tout en changeant les paires reliées doit produire un cas distinct.

Le cas n = 1 contient bien un arbre réduit à un sommet, mais l'énoncé source de la formule commence à n = 2. Il vaut mieux traiter ce cas séparément que manipuler l'exposant −1 comme s'il provenait d'un code de Prüfer ordinaire.

Une permutation des étiquettes ne crée pas automatiquement un nouvel ensemble d'arêtes. Sur l'étoile de l'exemple, échanger les feuilles 1 et 3 laisse les arêtes 1–2 et 2–3 présentes. Le critère sûr consiste à comparer les ensembles de paires étiquetées : seuls deux ensembles différents représentent deux arbres différents.

Le nombre nⁿ⁻² n'englobe ni les graphes déconnectés ni ceux qui contiennent un cycle, une boucle ou plusieurs arêtes entre les mêmes sommets. Le symptôme est immédiat : l'objet n'est plus un arbre simple. Il faut définir la nouvelle famille avant de la dénombrer.

La bijection de Prüfer donne davantage qu'une preuve numérique : elle transforme chaque arbre étiqueté en une suite finie et permet de revenir sans ambiguïté à l'arbre. Refaire l'encodage de l'arbre aux arêtes 1–2, 2–3 et 2–4 conduit au code (2, 2), ce qui vérifie les deux sens de la correspondance sur l'exemple.

L'histoire du résultat invite aussi à distinguer la démonstration par un déterminant d'une formule équivalente par Karl Borchardt en 1860 de sa formulation en termes d'arbres et du raffinement selon les degrés publiés par Arthur Cayley en 1889. Le nom resté dans la littérature ne résume donc pas, à lui seul, la chronologie mathématique.