En matemáticas , la fórmula de Cayley es un resultado de la teoría de grafos que lleva el nombre de Arthur Cayley . Establece que para cada entero positivo , la cantidad de árboles en los vértices etiquetados es .
La fórmula cuenta de manera equivalente el número de árboles de expansión de un gráfico completo con vértices etiquetados (secuencia A000272 en la OEIS ).
Se conocen muchas pruebas de la fórmula del árbol de Cayley. [1] Una prueba clásica de la fórmula utiliza el teorema del árbol matricial de Kirchhoff , una fórmula para el número de árboles de expansión en un grafo arbitrario que involucra el determinante de una matriz . Las sucesiones de Prüfer producen una prueba biyectiva de la fórmula de Cayley. Otra prueba biyectiva, de André Joyal , encuentra una transformación uno a uno entre árboles de n nodos con dos nodos distinguidos y pseudobosques dirigidos máximos . Una prueba por doble conteo debido a Jim Pitman cuenta de dos maneras diferentes el número de diferentes secuencias de aristas dirigidas que se pueden agregar a un grafo vacío en n vértices para formar a partir de él un árbol enraizado; consulte Doble conteo (técnica de prueba) § Conteo de árboles .
La fórmula fue descubierta por primera vez por Carl Wilhelm Borchardt en 1860 y demostrada mediante un determinante . [2] En una breve nota de 1889, Cayley extendió la fórmula en varias direcciones, teniendo en cuenta los grados de los vértices. [3] Aunque hizo referencia al artículo original de Borchardt, el nombre "fórmula de Cayley" se convirtió en estándar en el campo.
La fórmula de Cayley proporciona inmediatamente el número de bosques con raíces etiquetados en n vértices, es decir ( n + 1) n − 1 . Cada bosque con raíces etiquetado se puede convertir en un árbol etiquetado con un vértice adicional, agregando un vértice con la etiqueta n + 1 y conectándolo a todas las raíces de los árboles en el bosque.
Existe una estrecha conexión entre los bosques enraizados y las funciones de estacionamiento , ya que el número de funciones de estacionamiento en n automóviles también es ( n + 1) n − 1 . MP Schützenberger propuso una biyección entre los bosques enraizados y las funciones de estacionamiento en 1968. [4]
La fórmula de Cayley se generaliza a los bosques etiquetados: sea T n , k el número de bosques etiquetados en n vértices con k componentes conectados, de modo que los vértices 1, 2, ..., k pertenecen a diferentes componentes conectados. Entonces T n , k = k n n − k − 1 . [5]
