En matemáticas , la fórmula de Cayley es un resultado en la teoría de grafos que lleva el nombre de Arthur Cayley . Afirma que para cada entero positivo , el número de árboles envé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 ).
Prueba
Se conocen muchas pruebas de la fórmula del árbol de Cayley. [1] Una demostración clásica de la fórmula utiliza el teorema del árbol de matrices de Kirchhoff , una fórmula para el número de árboles de expansión en un gráfico arbitrario que involucra el determinante de una matriz . Las secuencias de Prüfer dan 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 pseudoforestales dirigidos máximos . Una prueba de conteo doble debido a Jim Pitman cuenta de dos maneras diferentes el número de secuencias diferentes de aristas dirigidas que se pueden agregar a un gráfico vacío en n vértices para formar a partir de él un árbol con raíces; ver Recuento doble (técnica de prueba) § Contar árboles .
Historia
La fórmula fue descubierta por primera vez por Carl Wilhelm Borchardt en 1860 y se demostró a través de 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 se refirió al artículo original de Borchardt, el nombre "fórmula de Cayley" se convirtió en estándar en el campo.
Otras propiedades
La fórmula de Cayley da inmediatamente el número de bosques enraizados etiquetados en n vértices, a saber ( n + 1) n - 1 . Cada bosque enraizado 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 con 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 dio una biyección entre bosques enraizados y funciones de estacionamiento en 1968. [4]
Generalizaciones
Lo siguiente generaliza la fórmula de Cayley 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 todos a diferentes componentes conectados. Entonces T n , k = k n n - k - 1 . [5]
Referencias
- ^ Aigner, Martin ; Ziegler, Günter M. (1998). Pruebas del LIBRO . Springer-Verlag . págs. 141-146.
- ^ Borchardt, CW (1860). "Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung". Matemáticas. Abh. der Akademie der Wissenschaften zu Berlin : 1–20.
- ^ Cayley, A. (1889). "Un teorema sobre árboles" . Cuarto de galón. J. Pure Appl. Matemáticas . 23 : 376–378.
- ^ Schützenberger, MP (1968). "Sobre un problema de enumeración". Revista de teoría combinatoria . 4 : 219-221. Señor 0218257 .
- ^ Takács, Lajos (marzo de 1990). "Sobre la fórmula de Cayley para contar bosques" . Revista de Teoría Combinatoria, serie A . 53 (2): 321–323. doi : 10.1016 / 0097-3165 (90) 90064-4 .