Demostración de la fórmula de Cayley generalizada

Question

Me gustaría probar la siguiente ecuación:

$$x_1x_2x_3...x_n(x_1 + x_2 + ... x_n)^{n-2} = \sum_Tx_1^{d_{T(1)}}x_2^{d_{T(2)}}...x_n^{d_{T(n)}}\tag 1$$

donde la suma es sobre todos los árboles de extensión $T$ en $K_n$ y $d_{T(i)}$ es el grado de $i$ en $T$

---

He oído que esto se llama la fórmula generalizada de Cayley, que es el número de $trees$ en $n$ vértices:

$n^{n-2} \tag 2$

Sólo la similitud morfológica entre $(1)$ y $(2)$ es la potencia $n-2$ .

Creo que en este caso la inducción podría funcionar bien, pero honestamente $induction$ sí mismo no es una forma productiva de probar algo para revelar la identidad matemática de uno a mí incluyendo este caso, la prueba de $(1)$ .

¿Alguna pista para demostrar esta ecuación de forma combinatoria y algebraica?

Answer 1

Dividamos ambos lados de $(1)$ por $x_1\dots x_n$ entonces tenemos que demostrar $$ (x_1 + x_2 + \dots + x_n)^{n-2} = \sum_{T}x_1^{d_{T(1)}-1}x_2^{d_{T(2)}-1}\dots x_n^{d_{T(n)}-1}. $$ Pero ahora el argumento es básicamente el mismo que La prueba de Prüfer . Obsérvese que cada vértice $T(i)$ se produce $d_{T(i)}-1$ veces (el número de pasos del algoritmo de Prüfer que se necesitan para $T(i)$ para convertirse en hoja) en la correspondiente secuencia de Prüfer, que tiene una longitud total $n-2$ . Por otro lado, cada término de la secuencia de Prüfer puede tomar cualquier valor de $1$ a $n$ por lo que corresponde a un factor de $x_1+\dots+x_n$ . Tenemos $n-2$ tales factores, lo que da lugar al lado izquierdo. Para derivar $(2)$ de $(1)$ , simplemente deja que $x_1=\dots=x_n=1$ .

Answer 2

Como habrás notado, la configuración de todos los $x_i$ a $1$ recupera el hecho de que el número de árboles en $n$ vértices, que es el mismo que el número de árboles que abarcan $K_n$ es $n^{n-2}$ .

Para obtener una prueba biyectiva de (1), dejemos que $x_1, \ldots, x_n$ son números que etiquetan los vértices de $K_n$ . Dado un árbol de expansión $T$ , tenga en cuenta que $$\prod_{(i,j) \in T} x_ix_j = \prod_{i = 1}^n x_i^{d_i(T)}.$$ (El producto de la izquierda es sobre bordes de $T$ .)

Suma de todos los árboles de extensión $T$ nos vemos reducidos a demostrar que $$\sum_{T} \prod_{(i, j) \in T} x_ix_j = x_1x_2\ldots x_n(x_1 + x_2 + \ldots + x_n)^{n-2}.$$

Nótese que el lado derecho es la suma sobre todos los monomios de grado $2n-2$ en el que cada variable tiene grado al menos $1$ . Ahora, dado cualquier conjunto $S$ de $n-1$ bordes $(u_i, v_i)$ en $K_n$ podemos formar el grado $2n-2$ monomio $$m(S) = \prod_{i=1}^{n-1} x_{u_i}x_{v_i}.$$ Además, si $S$ resulta ser un árbol de expansión, cada variable aparecerá al menos una vez.

Para completar la prueba, basta con demostrar que $m$ es una biyección entre el conjunto de árboles de extensión y los monomios de grado $2n-2$ en el que cada $x_i$ se produce al menos una vez. ¿Puedes llevarlo desde aquí?