Cómo probar $ \sum_{r=1}^{k-1} \binom{k}{r}\cdot r^r \cdot (k-r)^{k-r-1} = k^k-k^{k-1} $

Question

Cómo probar la siguiente identidad: $$ \sum_{r=1}^{k-1} \binom{k}{r}\cdot r^r \cdot (k-r)^{k-r-1} = k^k-k^{k-1} $$ No tengo ni idea de cómo abordarlo debido a la $r^r$ . ¡Cualquier ayuda es muy apreciada!

Answer 1

Podemos demostrarlo utilizando el árbol etiquetado función que se conoce de la combinatoria. La idea de que usemos una convolución es sólida, pero en realidad tenemos que hacer el álgebra.

Esto proporcionará una forma cerrada de la exponencial exponencial de los dos términos implicados.

Pretendemos demostrar que $$\sum_{r=1}^{k-1} {k\choose r} r^r (k-r)^{k-r-1} = k^k - k^{k-1}.$$

Obsérvese que cuando multiplicamos dos funciones generadoras exponenciales de las secuencias $\{a_n\}$ y $\{b_n\}$ conseguimos que

$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$

es decir, el producto de las dos funciones generadoras es la función generadora función de $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

En este caso tenemos $$A(z) = \sum_{q\ge 1} \frac{q^q}{q!} z^q \quad\text{and}\quad B(z) = \sum_{q\ge 1} \frac{q^{q-1}}{q!} z^q.$$

La especie de los árboles etiquetados tiene la especificación $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = \mathcal{Z} \times \textsc{SET}(\mathcal{T})$$ que da la ecuación funcional $$T(z) = z \exp T(z).$$

Extrayendo los coeficientes mediante la inversión de Lagrange tenemos $$Q_n = n! \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) dz.$$

Poner $T(z)=w$ para que $z=w/\exp(w) = w\exp(-w)$ y $dz = \exp(-w) - w\exp(-w) \; dw$ para conseguir $$n! \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(w(n+1))}{w^{n+1}} \times w\times (\exp(-w) - w\exp(-w)) dw \\ = n! \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(wn)}{w^n} (1 - w) dw.$$

Pero tenemos $$n! [w^{n-1}] \exp(w n) = n! \times \frac{n^{n-1}}{(n-1)!} = n^n$$ y $$n! [w^{n-2}] \exp(w n) = n! \times \frac{n^{n-2}}{(n-2)!} = n (n-1) n^{n-2} = (n-1) n^{n-1}$$ lo que significa que $T(z)$ es la función generadora exponencial de $$n^n - (n-1) n^{n-1} = n^{n-1} \quad\text{i.e.}\quad T(z) = \sum_{q\ge 1} \frac{q^{q-1}}{q!} z^q.$$ Esto también se deduce del teorema de Cayley.

La igualdad que pretendemos demostrar es la convolución de las dos funciones generadoras exponenciales $A(z)$ y $B(z)$ y para verificarlo debemos demostrar que $$k! [z^k] A(z) B(z) = k^k - k^{k-1}.$$ Pero tenemos (diferenciar los términos) $$A(z) = z \frac{d}{dz} T(z) \quad\text{and}\quad B(z) = T(z).$$

Observe que $$z T'(z) = z \left(\exp T(z) + z \exp T(z) T'(z) \right) = T(z) + z T(z) T'(z)$$ lo que implica que $$z T'(z) = \frac{T(z)}{1-T(z)}.$$

De ello se desprende que $$k! [z^k] A(z) B(z) = k! \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \frac{T(z)^2}{1-T(z)} dz.$$ Utilizando la misma sustitución que antes, esto se convierte en $$k! \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(w(k+1))}{w^{k+1}} \times \frac{w^2}{1-w}\times (\exp(-w) - w\exp(-w)) dw \\ = k! \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(wk)}{w^{k-1}} dw = k! \frac{k^{k-2}}{(k-2)!} = (k-1) k^{k-1} = k^k - k^{k-1}.$$

El función de árbol etiquetado apareció recientemente en este Enlace MSE .

Answer 2

Esta identidad es un caso especial de La identidad de Abel que a veces se considera como profundo generalización del teorema del binomio. Esta formulación puede encontrarse, por ejemplo, en el clásico Combinatoria avanzada por Louis Comtet en la sección 3.1. La identidad se enuncia allí en la forma \begin{align*} \sum_{k=0}^n\binom{n}{k}x(x-kz)^{k-1}(y+kz)^{n-k}=(x+y)^{n} \end{align*} válido para todo x,y,z en un anillo conmutativo. Si ponemos $z=0$ recuperamos la identidad binomial.

Una prueba bastante elemental de la afirmación de OPs se da en esta respuesta .

Con la convención habitual $0^0:=1$ se puede empezar la suma con $r=0$ y escribir la fórmula como \begin{align*} \sum_{r=0}^{k-1} \binom{k}{r} r^r (k-r)^{k-r-1} = k^k \end{align*} Revertir la suma $r \rightarrow k-1-r$ da \begin{align*} \sum_{r=0}^{k-1} \binom{k}{r+1} (k-r-1)^{k-r-1} (r+1)^{r+1} = k^k \end{align*} Finalmente desplazando el índice $r$ por uno es precisamente la identidad que se demuestra en el respuesta referida . \begin{align*} \sum_{r=1}^{k} \binom{k}{r} r^r(k-r)^{k-r} = k^k \end{align*}

Answer 3

También hay una prueba combinatoria rápida. Ambos lados de la ecuación responden a la pregunta

¿Cuántas formas hay de elegir un árbol rooteado en los distintos vértices $\{1,2,\dots,k\}$ y luego elegir uno de los bordes?

El lado derecho es $(k-1)k^{k-1}$ . Interpretamos $k^{k-1}$ como el número de árboles enraizados en $k$ vértices, mientras que $(k-1)$ da la elección de un borde.

Dado un árbol rooteado en $k$ vértices, junto con una arista distinguida, la eliminación de la arista deja dos árboles desconectados, uno de los cuales contiene la raíz del árbol original. Se deduce que otra forma de elegir un árbol con raíz y arista distinguida es...

• Seleccione $r$ vértices de $\{1,2,\dots,k\}$ , en $\binom{k}r$ formas,
• Elija un árbol rooteado en estos $r$ vértices en $r^{r-1}$ formas,
• Elija un sin raíces árbol en el resto de $k-r$ vértices en $(k-r)^{k-r-2}$ formas, y
• Elija un vértice del árbol rooteado (en $r$ formas) y un vértice del árbol no rooteado (en $k-r$ formas) y unirlas con un borde distinguido.