Cómo puedo probar la identidad de $2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}$?

Question

Cómo puedo probar la identidad

$$2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}?$$

Sé que el número de árboles en $n$ vértices es $n^{n-2}$, y que un árbol con $n$ vértices ha $n-1$ bordes, pero no sé cómo continuar. Me podrían ayudar por favor?

Answer 1

El OP está en la dirección correcta. Por Cayley de la fórmula, el número de la etiqueta de árboles en $n$ vértices es $n^{n-2}$. Vamos a contar el número de árboles etiquetados de una manera diferente y conseguir la igualdad.

Tome un árbol de $T$ y un borde de $e \in T$. A continuación, $T \setminus \{ e \}$ contiene dos componentes, a decir de los tamaños de las $k$$n-k$. También, cada uno de los componentes es un árbol por sí mismo. Con esto en mente, vamos a construir el árbol de $T$ como sigue. Partición de los vértices en dos partes, de los tamaños de las $k$ $n-k$ respectivamente. Dibujar árboles $T_1$ $T_2$ en las dos partes. A continuación, elegir un vértice arbitrario de cada una de las partes y unirse a la par por un borde.

El número de maneras de hacer este procedimiento es: $$ \sum_{k=1}^{n-1} \binom{n}{k} \times k^{k-2} (n-k)^{n-k-2} \times (k (n-k)) = R, $$ el lado derecho de la supuesta ecuación. El coeficiente binomial surge de la elección de $k$ vértices. El segundo factor es mediante la aplicación de la Cayley la fórmula para el número de árboles en $k$ $n-k$ vértices. El $k(n-k)$ factor es el número de maneras de conectar estos componentes por un solo borde.

Ahora, este procedimiento overcounts el número de árboles. Específicamente, cada árbol puede ser cortado en cualquier de sus $n-1$ bordes para dar un par de componentes. (Que es un factor de $n-1$.) Además, en la selección de $k$ vértices para hacer dos componentes de tamaños de $k$$n-k$, podemos distinguir los dos componentes (uno que se ha seleccionado, y uno que no lo es). Así pues, debemos dividir el número conseguimos por $2$.

Por lo tanto el número de marcado de árboles en $n$ vértices es $$ \frac{R}{2(n-1)}. $$ La equiparación de la a $n^{n-2}$, se obtiene la demanda.

Answer 2

El Lambert función tiene la siguiente serie de Maclaurin:

$$-W(-x)=\sum_{k=1}^\infty \frac{k^{k-1}}{k!} x^k$$

(En algunas referencias, $-W(-x)$ se conoce como el "árbol de la función", $T(x)$, como se trata de una generación de función para arraigada la etiqueta de árboles).

Esta serie puede ser derivada a través de Lagrange de la inversión. En particular, el coeficiente de $x^k$ en el poder de la serie de el árbol de la función está dada por la expresión

$$\frac1{k!}\left.\dfrac{\mathrm d^{k-1}}{\mathrm dt^{k-1}}\left(\frac{t}{t\exp(-t)}\right)^k\right\vert_{t=0}=\frac{k^{k-1}}{k!}$$

La ecuación original puede ser re-expresadas como

$$\frac{2(n-1)n^{n-2}}{n!}=\sum_{k=1}^{n-1} \frac{k^{k-1}}{k!}\frac{(n-k)^{n-k-1}}{(n-k)!}$$

El lado derecho es la autoconvolution de la secuencia de $\dfrac{k^{k-1}}{k!}$; de ordinario, la generación de la función es, pues, la plaza de la generación de la función de $\dfrac{k^{k-1}}{k!}$,$(-W(-x))^2=W(-x)^2$.

Para encontrar una expresión para la serie coeficiente de $W(-x)^2$, podemos considerar en primer lugar las relacionadas con la función de $\left(\dfrac{W(-x)}{-x}\right)^2-1=\exp(-2\,W(-x))-1$. Esta función es la inversa de a $\dfrac{\log\sqrt{1+x}}{\sqrt{1+x}}$. La aplicación de Lagrange de la inversión a $\dfrac{\log\sqrt{1+x}}{\sqrt{1+x}}$ y el uso de los resultados obtenidos en esta respuesta, se obtiene la serie

$$\left(\frac{W(-x)}{-x}\right)^2-1=\sum_{k=1}^\infty \frac{2(k+2)^{k-1}}{k!}x^k$$

que reorganiza a

$$W(-x)^2=\sum_{k=0}^\infty \frac{2(k+2)^{k-1}}{k!}x^{k+2}$$

y también puede ser expresado como

$$W(-x)^2=\sum_{k=1}^\infty \frac{2(k-1) k^{k-2}}{k!} x^k$$

lo que demuestra la expresión más sencilla de la autoconvolution.

La última serie también aparece como la fórmula 11 de este documento por Corless, Jeffrey, y Knuth, así como los que aparecen en una forma encubierta como ecuación 5.60 en Concreto de las Matemáticas.