Experimentando con la serie de representaciones de $e^{x e^x}$ me llegó a través de los dos aparentemente diferentes de alimentación de la serie $$e^{x e^x} = \sum_{n=0}^{\infty} x^n \sum_{k=0}^{n} \frac{(n-k)^k}{(n-k)! \cdot k!}$$ y $$e^{x e^x} = \sum_{n=0}^{\infty} x^n \sum_{k=0}^{n} \frac{1}{(n-k)!} \sum_{i=0}^{k} \frac{1}{(k-i)!} {k-i \brace i}\,.$$ Deben ser y son de hecho idénticos. Por la equiparación de los coeficientes es obvio que $$\sum_{k=0}^{n} \frac{(n-k)^k}{(n-k)! \cdot k!} = \sum_{k=0}^{n} \frac{1}{(n-k)!} \sum_{i=0}^{k} \frac{1}{(k-i)!} {k-i \brace i}\,.$$ Ir a través de algunos de los valores de $n$ asegura la exactitud de la ecuación, sin embargo no tengo idea de cómo se podría mostrar de esta manera algebraica. Una ecuación equivalente sería $$\sum_{k=0}^{n} {n \choose k} (n-k)^k = \sum_{k=0}^{n} {n \choose k} \sum_{i=0}^{k} {k \choose i} \sum_{j=1}^{i} (-1)^{i-j} {i \choose j} j^{k-i}\,,$$ que se obtiene a través de la multiplicación de ambos lados de la $n!$ y una fórmula explícita para los números de Stirling. No importa lo que yo trato, me parece que en una pared de ladrillo. ¿Cómo puedo (algebraicamente) demostrar que la ecuación es correcta para arbitrario $n$?
Respuestas
¿Demasiados anuncios?Supongamos que buscan una alternativa a la representación de
$$\sum_{k=0}^n \frac{(n-k)^k}{(n-k)! \times k!}$$
en términos de números de Stirling. Vamos a utilizar el conjunto de especies de las particiones que es
$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$
que los rendimientos de la generación de la función
$$G(z, u) = \exp(u(\exp(z)-1))$$
que a su vez produce inmediatamente que
$${n\brace q} = n! [z^n] \frac{(\exp(z)-1)^q}{q!}.$$
Podemos empezar con el cálculo por re-indexación para obtener
$$\sum_{k=0}^n \frac{k^{n-k}}{(n-k)! \times k!}.$$
Tenga en cuenta que
$$k^{n-k} = (n-k)! \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \exp(kz) \; dz.$$
Por lo tanto
$$\frac{k^{n-k}}{(n-k)!} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \exp(kz) \; dz.$$
Observar que este se desvanece al $k\gt n$ (y se proporciona un valor de cero para $k\gt n$ donde $(n-k)!$ no está definido) por lo que tiene un built-in rango de aplicación y se puede extender a la suma de los infinitos términos. De este modo, obtener
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{k\ge 0} \frac{1}{k!} z^k \exp(kz) \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(z\exp(z)) \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(z) \exp(z(\exp(z)-1)) \; dz.$$
La extracción de los coeficientes de ahora rendimientos
$$\sum_{k=0}^n \frac{1}{(n-k)!} [z^k] \exp(z(\exp(z)-1)) \\ = \sum_{k=0}^n \frac{1}{(n-k)!} [z^k] \sum_{q=0}^\infty \frac{z^p}{q!} (\exp(z)-1)^q \\ = \sum_{k=0}^n \frac{1}{(n-k)!} \sum_{q=0}^k [z^{k-q}] \frac{1}{p!} (\exp(z)-1)^q \\ = \sum_{k=0}^n \frac{1}{(n-k)!} \sum_{q=0}^k \frac{1}{(k-q)!} {k-q\llave q}.$$
Este es el reclamo.
Aquí está una combinatoria de la prueba; es probable que esto se puede convertir en una prueba algebraica (en el sentido de manipulación algebraica de las cantidades) con un poco de esfuerzo. La combinatoria le dirá lo que necesita para que se vuelvan a indexar para conseguir que las cosas funcionen.
Esta es una exponencial de generación de función, por lo que una pregunta natural es lo que la secuencia es la exponencial de la generación de la función de. La respuesta, que puede ser deducido a partir de una versión adecuada de la fórmula exponencial, es:
El coeficiente de $\frac{x^n}{n!}$ $e^{xe^x}$ cuenta el número de maneras de partición de un conjunto $N$ $n$ elementos en subconjuntos no vacíos, entonces distinguir un elemento de cada subconjunto.
El LHS cuenta los pares que consiste en un subconjunto $K$ $N$ y una función de $K \to N \setminus K$. Por eso queremos demostrar que esto es en bijection con el anterior. El bijection resulta ser que $N \setminus K$ es el conjunto de distinguidos elementos, y la preimages de la función $K \to N \setminus K$ dar el resto de las particiones de los distinguidos elementos.
El RHS cuenta tuplas que consta de
- un subconjunto $K$$N$,
- un subconjunto $I$$K$,
- una partición de $K \setminus I$ a $|I|$ no vacía de subconjuntos, y
- un bijection entre el $I$ y las particiones de $K \setminus I$.
De nuevo queremos mostrar esto es en bijection con el anterior. Aquí el bijection resulta ser que $N \setminus K$ es el conjunto de distinguidos elementos tales que la partición en la que está no tiene otros elementos. Todas las otras particiones tienen al menos otro elemento, y los distinguidos elementos para aquellos que corresponden a $I$, mientras que el resto de las particiones se corresponden con el vacío particiones de $K \setminus I$.
Aquí es otra variación del tema. Con el fin de demostrar el binomio identidad \begin{align*} \sum_{k=0}^{n} \binom{n}{k} (n-k)^k =\sum_{k=0}^{n} \binom{n}{k} \sum_{i=0}^{k}\binom{k}{i} \sum_{j=0}^{i}\binom{i}{j} (-1)^{i-j} j^{k-i}\tag{1} \end{align*}
echamos un vistazo a una binomial inversa par. Deje $F(x)=\sum_{n=0}^\infty f_n \frac{x^n}{n!}$ $G(x)=\sum_{n=0}^\infty g_n \frac{x^n}{n!}$ ser exponencial en la generación de funciones. Consideramos los siguientes
Binomial inversa par: \begin{align*} F(x)&=G(x)e^x&G(x)&=F(x)e^{-x}\\ f_n&=\sum_{k=0}^{n}\binom{n}{k}g_k&g_n&=\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}f_k\qquad \tag{2} \end{align*}
Este simple y muchos otros ejemplos de la binomial inversa pares se pueden encontrar por ejemplo, en el clásico de la Combinatoria de las Identidades por John Riordan ($1968$).
Podemos obtener a partir de (2) por la sucesiva sustitución de $f_n$ resp. $g_n$ \begin{align*} f_n&=\sum_{k=0}^{n}\binom{n}{k}g_k\tag{3}\\ &=\sum_{k=0}^{n}\binom{n}{k}\sum_{i=0}^k\binom{k}{i}(-1)^{k-i}f_i\\ &=\sum_{k=0}^{n}\binom{n}{k}\sum_{i=0}^k\binom{k}{i}(-1)^{k-i}\sum_{j=0}^{i}\binom{i}{j}g_j\tag{4} \end{align*}
Establecimiento $g_k=k^{n-k}$ obtenemos de (3) y (4)
El siguiente es válido para $n\geq 0$: \begin{align*} \sum_{k=0}^{n}\binom{n}{k}k^{n-k}=\sum_{k=0}^{n}\binom{n}{k}\sum_{i=0}^k\binom{k}{i}(-1)^{k-i}\sum_{j=0}^{i}\binom{i}{j}j^{i-j}\tag{5} \end{align*}
Observar el lado izquierdo de (5) corresponde al lado izquierdo de (1) reemplazando $k\rightarrow n-k$. Por lo tanto, estamos casi terminado.
Por último tenemos que mostrar el lado derecho de (5) es igual para el lado derecho de (1). Tenga cuidado, aunque se ven del mismo modo, no son las mismas!
La validez de \begin{align*} \sum_{k=0}^{n} \binom{n}{k} \sum_{i=0}^{k}\binom{k}{i}\sum_{j=0}^{i}\binom{i}{j} (-1)^{i-j} j^{k-i} =\sum_{k=0}^{n}\binom{n}{k}\sum_{i=0}^k\binom{k}{i}\sum_{j=0}^{i}\binom{i}{j}(-1)^{k-i}j^{i-j} \end{align*} se muestra en esta pregunta y la afirmación de la siguiente manera.
Nota: Durante el análisis de la identidad, cuando tuve la asociación con la binomial inversa pares yo estaba bastante seguro de que, de que las expresiones (4) y (5) en caso de ya el resultado en el lado derecho de (1). Fue realmente sorprendente ver que este no era el caso y se necesita una cantidad considerable de esfuerzo para completar la respuesta.