formule de Cayley
COMBINATOIRE
La formule de Cayley est un résultat de théorie des graphes, il porte sur les arbres de Cayley.
Enoncé : Le nombre d’arbres différents (non orientés) que l’on peut construire sur n sommets numérotés, avec n>1 est égal à nn-2.
Les sommets sont identifiés par exemple par des couleurs. On parle d’arbres décorés ou étiquetés ou encore d’arbres de Cayley.
Exemples : * avec 2 sommets , 1 seul arbre
* avec 3 sommets 3 arbres
* avec 4 sommets 16 arbres
Cette formule a été découverte par Karl Borchardt (en 1860), puis Cayley l’a étendu en 1889. C’est cependant le nom formule de Cayley qui a été retenu.