Fòrmula de Cayley

Llistacompleta de tots els arbres en 2,3 i 4 vèrtiços etiquetats: $2^{2-2}=1$ arbres en 2 vèrtiços, $3^{3-2}=3$ arbres en 3 vèrtiços i $4^{4-2}=16$ arbres en 4 vèrtiços.

En teoria de grafos, la fòrmula de Cayley és un resultat cridat aixina en honor a Arthur Cayley, que establix que per a qualsevol sancer positiu n, el número d'arbres en n vèrtiços etiquetages és $n^{n-2}$.

Equivalentement, la fòrmula conta el número d'arbres d'expansió d'un grafo complet en vèrtiços etiquetats.

Demostració

Es coneixen moltes demostracions per a esta fòrmula. Una demostració clàssica utilisa el teorema de Kirchhoff. Les seqüències de Prüfer otorguen una demostració biyectiva de la fòrmula de Cayley. Una atra demostració biyectiva, d'André Joyal, troba una demostració un-a-un entre arbres de n vèrtiços en dos nodos distinguibles i pseudobosques dirigits.

Història

La fòrmula va ser descoberta per Carl Wilhelm Borchardt en 1860, i demostrada a través d'un determinant. En una chicoteta nota de 1889, Cayley va estendre la fòrmula en moltes direccions, prenent en conte el grau dels vèrtiços. Encara que Cayley referenció l'artícul original de Borchardt, és el nom de "fòrmula de Cayley" el que es va convertir en estàndart dins del camp.

Referències

• .
• Borchardt, C.W.(1860).«Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung».

1–20.

• A. Cayley(1889).«A theorem on trees».23

376–378.

• .