Formule de Cayley
En mathématiques, et plus particulièrement en théorie des graphes, la formule de Cayley est un résultat sur les arbres du théoricien Arthur Cayley. Elle affirme le résultat suivant : Note : on parle aussi d'arbres décorés ou étiquetés pour dire que l'on identifie les sommets avec des couleurs, des nombres, etc. On parle aussi d'arbres de Cayley. Pour l'exemple illustré ci-contre, on obtient les résultats suivants, en appliquant le théorème : 1 arbre avec 2 sommets, 3 arbres avec 3 sommets, 16 arbres avec 4 sommets. Cette formule a d'abord été découverte par Karl Wilhelm Borchardt en 1860 et prouvée à l'aide d'un déterminant. Dans une brève note en 1889, Arthur Cayley a étendu la formule dans plusieurs directions, en tenant compte du degré des sommets. Bien que Cayley ait mentionné le travail de Borchardt, le nom « formule de Cayley » est resté attaché à cette formule. On connaît plusieurs preuves remarquables de la formule de Cayley. Une démonstration classique utilise le théorème de Kirchhoff, un théorème plus puissant qui donne le nombre d'arbres couvrants pour un graphe quelconque, alors que la formule de Cayley ne donne ce nombre que pour les graphes complets. Théorème de Kirchhoff Une démonstration élégante est due à André Joyal. Pour compter les éléments de l'ensemble des arbres numérotés à n sommets, il établit une bijection entre et l'ensemble des applications de dans , noté usuellement . On a ainsi Bijection de Joyal Une autre démonstration élégante est due à Heinz Prüfer. Le codage de Prüfer établit une bijection de vers l'ensemble des (n-2)-uplets à valeurs prises dans l'intervalle , or le cardinal de ce dernier vaut . Codage de Prüfer Une dernière démonstration élégante par double dénombrement a été apportée par Jim Pitman. Il compte de deux façons différentes les suites d'arêtes orientées formant des arbres couvrant les n sommets, et obtient et arêtes orientées couvrant les n sommets. Il en déduit la formule de Cayley. Preuve par double dénombrement#Compter les arbres Martin Aigner et Günter M.
