Prueba intuitiva de $\sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k} = n^n$

Question

¿Existe una manera intuitiva, aunque tampoco estoy seguro de cómo encontrar una prueba conceptual, de establecer la siguiente identidad? $$\sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k} = n^n$$ para todos los números naturales.

Estoy pensando en la fórmula binomial $$\sum_{k=0}^n\binom nk x^{n-k}y^k=(x+y)^n$$ pero no estoy seguro de cómo usarlo.

Este problema me parece tentador porque parece que debería haber algún tipo de forma intuitiva, así que por eso lo comparto aquí. Estoy buscando una respuesta como mi pregunta antes si es posible. ¿Puedes encontrar uno?

Answer 1

Esta es una bonita variante 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}\tag{1} \end{align*} válido para todo x,y,z en un anillo conmutativo. Si ponemos $z=0$ recuperamos la identidad binomial.

En un comentario a la pregunta de OPs @ArtW se refiere a un papel de Wengchang Chu que presenta una prueba instructiva y elemental que es la base de esta respuesta.

Prueba de la identidad de Abel

De hecho, es más conveniente demostrar una versión generalizada de la afirmación de la OP. En un segundo paso demostramos que la fórmula de OP es una variante particular de la identidad general. Demostramos la identidad (1) en el caso especial $z=-1$ que es apropiado para nosotros y el espectáculo:

Es válido lo siguiente \begin{align*} \sum_{k=0}^n\binom{n}{k}x(x+k)^{k-1}(y-k)^{n-k}=(x+y)^n\tag{2} \end{align*}

Obtenemos \begin{align*} \sum_{k=0}^n&\binom{n}{k}x(x+k)^{k-1}(y-k)^{n-k}\\ &=\sum_{k=0}^n\binom{n}{k}x(x+k)^{k-1}((x+y)-(x+k))^{n-k}\tag{3}\\ &=\sum_{k=0}^n\binom{n}{k}x(x+k)^{k-1}\sum_{j=0}^{n-k}\binom{n-k}{j}(-1)^j(x+k)^j(x+y)^{n-k-j}\tag{4}\\ &=\sum_{k=0}^n\binom{n}{k}x(x+k)^{k-1}\sum_{j=k}^{n}\binom{n-k}{j-k}(-1)^{j-k}(x+k)^{j-k}(x+y)^{n-j}\tag{5}\\ &=\sum_{k=0}^n\sum_{j=k}^{n}\binom{n}{k}x(x+y)^{n-j}\binom{n-k}{j-k}(-1)^{j-k}(x+k)^{j-1}\tag{6}\\ &=\sum_{j=0}^n\binom{n}{j}x(x+y)^{n-j}\sum_{k=0}^{j}\binom{j}{k}(-1)^{j-k}(x+k)^{j-1}\tag{7}\\ &=(x+y)^n\tag{8} \end{align*} y (2) sigue.

Comentario:

• En (3) sustituimos $y-k$ con $(x+y)-(x+k)$ sin cambiar nada, ya que sólo estamos añadiendo el cero.

• En (4) aplicamos la _teorema del binomio_ a $$((x+y)-(x+k))^{n-k}$$

• En (5) desplazamos el índice $j$ por $k$ en la suma interna

• En (6) recogemos los factores de $(x+k)$ e intercambiar la suma interna y externa respetando \begin{align*} \sum_{k=0}^n\sum_{j=k}^n a_{j,k}=\sum_{0\leq k\leq j\leq n} a_{j,k}=\sum_{j=0}^n\sum_{k=0}^ja_{j,k} \end{align*}

• En (7) utilizamos la identidad \begin{align*} \binom{n}{k}\binom{n-k}{j-k}=\binom{n}{j}\binom{j}{k} \end{align*}

• En (8) observamos que la suma interna es un polinomio en $k$ de grado $j-1$ . También observamos que el _operador de diferencia_ $\Delta$ \begin{align*} \Delta f(x)=f(x+1)-f(x) \end{align*} cuando se aplica a un polinomio reduce el grado en uno. Como la suma interna de (8) es el operador Delta aplicado $j$ veces al polinomio $(x+k)^{j-1}$ (ver la página Wiki referida para esto) y el grado del polinomio es menor que $j$ , es se desvanece siempre que $j>0$ . \begin{align*} \Delta^{j}(x+k)^{j-1}=\sum_{k=0}^j\binom{j}{k}(-1)^{j-k}(x+k)^{j-1}=0\qquad\qquad j>0 \end{align*} Por lo tanto, sólo tenemos que considerar $j=0$ en (7) dando como resultado $(x+y)^n$ .

Derivación de la fórmula OPs

Podemos escribir la identidad de Abel (2) en el caso $x\ne 0$ en la forma \begin{align*} \sum_{k=1}^n\binom{n}{k}(x+k)^{k-1}(y-k)^{n-k}=\frac{(x+y)^n-y^n}{x} \end{align*}

Dejar $x\rightarrow 0$ obtenemos \begin{align*} \sum_{k=1}^n\binom{n}{k}k^{k-1}(y-k)^{n-k}=ny^{n-1} \end{align*}

Por fin poner $y=n$ obtenemos \begin{align*} \sum_{k=1}^n\binom{n}{k}k^{k-1}(n-k)^{n-k}=n^n \end{align*} y la afirmación de OPs sigue.

Note : La identidad de Abel tiene muchas formas diferentes. Se puede encontrar una buena colección en _este documento_ por Stanislav Sykora. La identidad de OPs aparece como (13) en el documento. De forma divertida e indicando la belleza de la fórmula afirma en una nota a pie de página que precisamente este identidad fue el motivo de su recherche. También presenta una copia de la prueba original de Abel de 1826.

Answer 2

Sugerencia . Esto puede verse como un caso particular de la identidad binomial de Abel-Hurwitz, véase una explicación probabilística aquí . Las pruebas combinatorias se dan en las referencias $[8,11,19,21]$ de este papel . Véase también este papel .

Answer 3

También hay una prueba combinatoria de esto. $n^n=n\cdot n\cdot n^{n-2}$ cuenta el número de árboles etiquetados doblemente enraizados en el conjunto $N:=\{1,2,\dots,n\}$ . Describimos una biyección que toma un árbol doblemente rooteado $(T,u,v)$ a un par $\Big((T_1,r),(T_2,s,t)\Big)$ , donde

• $(T_1,r)$ es un árbol rooteado en un subconjunto no vacío $K$ de $N$ ,

• $(T_2,s,t)$ es un árbol doblemente rooteado en $N\setminus K$ . La única excepción es cuando $N\setminus K$ está vacío, en cuyo caso $T_2$ es el árbol vacío y no tiene raíces.

Esta biyección demuestra la igualdad deseada, ya que

• $k:=|K|$ puede ser cualquier número entre $1$ y $n$ ,
• hay $\binom{n}k$ formas de elegir $K$ ,
• hay $k^{k-1}$ para elegir un árbol rooteado etiquetado en $K$ ,
• hay $(n-k)^{n-k}$ formas de elegir un árbol etiquetado de doble raíz en $N\setminus K$ . Esto funciona incluso cuando $N\setminus K$ está vacío, ya que $0^0=1$ y hay un árbol vacío.

Aquí está la biyección. Dado el árbol doblemente rooteado $(T,u,v)$ Hay dos casos.

1. Si $u=v$ alors $K=N$ , $T_1=T$ , $r=u=v$ y $T_2$ está vacía.

2. En caso contrario, deja que $w$ sea el vértice adyacente a $u$ en el camino de $u$ a $v$ en $T$ . Si retira el borde $(u,w)$ alors $T$ se divide en dos árboles $T_1$ y $T_2$ , donde $u\in T_1$ y $w,v\in T_2$ . Dejamos que $u$ sea la raíz de $T_1$ y que $v$ y $w$ sean las raíces de $T_2$ .

Answer 4

Voy a responder a su solicitud de un manera intuitiva En primer lugar, permítanme resumir lo que ya se ha presentado en el respuestas y en las referencias dadas aquí y en el post relacionado. Luego mencionaré los resultados proporcionados en un trabajo posterior [3], que avanza en la generalización del teorema del binomio, y que ilustra mejor lo que sucede en esta escena tan interesante.

Así que la identidad de tu post es un caso particular de la forma más general de la Identidad de Abel, como en la respuesta de Markus, en la referencia [1] y en otros trabajos, que se puede escribir como $$ \tag{1} z^{\,n} = a\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( \begin{array}{c} n \\ k \\ \end{array} \right)\left( {a - kb} \right)^{\,k - 1} \left( {z - a + kb} \right)^{\,n - k} } $$ En passant nota que la "Serie Abel" $$ f(z) = \sum\limits_{0\, \le \,k} {\frac{{f^{\left( k \right)} \left( {k\,t} \right)}}{{k!}}z\left( {z - k\,t} \right)^{\,k - 1} } $$ daría por $z^n$ la identidad anterior con $a=z$ .

Ahora en [2] la Identidad de Abel se reescribe como:
$$ \tag{2.a} \frac{{z^{\,n} }}{{n!}} = \sum\limits_{0\, \le \,k\, \le \,n} {\frac{a}{{a - bk}}\frac{{\left( {a - bk} \right)^{\,k} }}{{k!}}} \frac{{\left( {z - \left( {a - bk} \right)} \right)^{\,n - k} }}{{\left( {n - k} \right)!}} $$ y paralela a la identidad de Hagen-Rothe $$ \tag{2.b} \left( \begin{array}{c} z \\ n \\ \end{array} \right) = \sum\limits_{0\, \le \,k\, \le \,n} {\frac{a}{{a - bk}}\left( \begin{array}{c} a - bk \\ k \\ \end{array} \right)} \left( \begin{array}{c} z - \left( {a - bk} \right) \\ n - k \\ \end{array} \right) $$ es decir: $$ \tag{2.c} \frac{{z^{\,\underline {\,n\,} } }}{{n!}} = \sum\limits_{0\, \le \,k\, \le \,n} {\frac{a}{{a - bk}}\frac{{\left( {a - bk} \right)^{\,\underline {\,k\,} } }}{{k!}}} \frac{{\left( {z - \left( {a - bk} \right)} \right)^{\,\underline {\,n - k\,} } }}{{\left( {n - k} \right)!}} $$ y se puede demostrar fácilmente que también es válida para el factorial ascendente $$ \tag{2.d} \frac{{z^{\,\overline {\,n\,} } }}{{n!}} = \sum\limits_{0\, \le \,k\, \le \,n} {\frac{a}{{a - bk}}\frac{{\left( {a - bk} \right)^{\,\overline {\,k\,} } }}{{k!}}} \frac{{\left( {z - \left( {a - bk} \right)} \right)^{\,\overline {\,n - k\,} } }}{{\left( {n - k} \right)!}} $$

En el artículo [3] los autores presentan y analizan cómo Gould ha ampliado la representación a $$ \tag{3} z^{\,n} = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( \begin{array}{c} n \\ k \\ \end{array} \right)\;c(k)\left( {z - \beta _{\,k} } \right)^{\,n - k} \,} $$ donde $\beta _{\,k} $ con $\beta _{\,0} \ne 0$ es una secuencia general (incluso compleja) y los coeficientes $c(k)$ con $c(0)=1$ se determinan de forma única por una relación de recurrencia que se determina fácilmente imponiendo que debe ser válida también para $z=0$ .
Tenga en cuenta que para los enteros $\beta _{\,k} $ El $c(k)$ también son enteros (y polinomios simétricos en $\beta _{\,k} $ ).
Tomando la secuencia lineal $\beta _{\,k} = a - bk$ luego da la identidad de Abel.

Finalmente llegamos a ver que la Identidad de Gould es sólo la representación del polinomio $z^n$ en la base dada por los polinomios ${\left( {z - \beta _{\,k} } \right)^{\,n - k} }$

---

Referencias
[1] "La identidad de un Abel y sus corolarios" - Stanislav Sykora - ExtraByte, Castano Primo (MI), Italia Ed. Junio 2014
http://ebyte.it/library/educart/math/2014_MATH_Sykora_AbelCorollaries.pdf
[2] "Pruebas elementales para las identidades de convolución de Abel y Hagen-Rothe" - Wenchang Chu - The Electronic Journal of Combinatorics - Vol.17 -2010 http://www.combinatorics.org/Volume_17/PDF/v17i1n24.pdf
[3] "Sobre los polinomios de Abel-Gontscharoff-Gould" - T. X. He, L. C. Hsu, P. J. S. Shiue - Illinois Wesleyan University http://sun.iwu.edu/~the/AGGpoly.pdf

Answer 5

Operador de diferencia: $\Delta f(k)=f(k+1)-f(k)$ obtenemos $$ \sum_{k=1}^n\Delta f(k)=f(n+1)-f(0), $$ y dejamos que $$ f(k)=\binom{x}k^p(k!)^py^{-kp}, $$ Aplicando a la ecuación anterior, obtenemos $$ \begin{aligned} \Delta f(k) &=\binom{x}{k+1}^p(k+1)!^py^{-kp-p}-\binom{x}k^p(k!)^py^{-kp}\\ &=\binom xk^p(k!)^py^{-p(k+1)}[(x-k)^p-y^p]\\ \end{aligned} $$ Utilizando la ecuación de la suma anterior, $$ \begin{aligned} &\sum_{k=0}^n\binom xk^p(k!)^py^{-p(k+1)}[(x-k)^p-y^p]\\ =&\binom x{n+1}^p(n+1)!^py^{-pn-p}-1, \end{aligned} $$ Ambos lados se multiplican juntos $y^{pn+p}$ obtenemos $$ \begin{aligned} &\sum_{k=0}^n\binom xk^p(k!)^py^{p(n-k)}[(x-k)^p-y^p]\\ =&\binom x{n+1}^p(n+1)!^p-y^{p(n+1)}, \end{aligned} $$ dejar $p=1,x=n-1,y=n$ y obtenemos $$ \sum_{0\leqslant k\leqslant n-1}\binom{n-1}kn^{n-1-k}(k+1)!=n^n. $$