En la lectura acerca de Una polarización de identidad para multilineal mapas por Erik G F Thomas, soy llevado a probar el siguiente combinatoria de identidad, que no puedo encontrar en cualquier lugar, ni tengo idea de cómo demostrarlo.
$$\sum\limits_{j=1}^k(-1)^{k-j}j^k\binom{k}{j}=k!.$$
Después de algunas reducciones (incluyendo $\binom{k+1}{j}=\binom{k}{j}+\binom{k}{j-1}$) y "simplificaciones", todavía estoy atascado y no tiene pistas sobre cómo proceder.
No sé si esto es cierto, aunque creo que debería ser.
Cualquier ayuda o referencia es sinceramente la bienvenida, gracias de antemano.
Esta pregunta ya tiene respuestas:
Respuestas
¿Demasiados anuncios?
Patrick Stevens
Puntos
5060
Una combinatoria de respuesta.
El lado derecho es el número de permutaciones de $\{0, 1, \dots, k-1\}$.
Voy a dejar de $k=5$ para la concreción.
Contamos con las permutaciones de otra manera. Tomar una $5$-tupla extraídas de $\{0,1,\dots,4\}$ - es decir, un miembro de $5^5$. Probablemente este no sea el de permutaciones - por ejemplo, podría ser $00000$.
Quite cualquier cosa que no contenga una $4$. Es decir, quitar todo aquello que puede extraerse de los $4^5$. Esto deja a todos los cambios, pero también deja las cosas como $44444$, lo que en realidad nos debería ser la eliminación de cualquier cosa que puede extraerse de los $\{ 1, 2, 3, 4\}$ e de $\{ 0, 2, 3, 4\}$ y así sucesivamente.
Es decir, eliminamos $4^5$ cosas $\binom{5}{1} = \binom{5}{4}$ veces.
OK, hemos dejado todas las permutaciones, pero ahora le he quitado algunas cosas más de una vez: nos quitan $00000$ porque no contiene un $4$, pero también porque no contiene un $3$, por ejemplo. En general, hemos eliminado dos veces cualquier cosa que tiene dos cosas que no contienen, y hemos eliminado tres veces todo lo que tenga tres cosas que no contienen, y así sucesivamente. Necesitamos volver a añadirlas en bastantes veces: tenemos que añadir una vez cualquier cosa que tiene dos cosas que no contienen, añadir el doble de todo lo que tenga tres cosas que no contienen, y así sucesivamente.
Agregar en $3^5$ cosas $\binom{5}{2}$ veces: es decir, agregar en cualquier cosa que no contenga una $0$ y no contiene un $1$, a continuación, añadir en cualquier cosa que no contenga una $0$ y no contiene un $2$, entonces... a continuación, añadir en cualquier cosa que no contenga una $3$ y no contiene un $4$. Hemos re-agregó algo que tiene dos cosas que no contienen, pero hemos re-añadió $\binom{3}{2}$ veces todo lo que tenga tres cosas que no contienen, re-añadió $\binom{4}{2}$ veces todo lo que tenga cuatro cosas que no contienen, y así sucesivamente.
Repita este procedimiento de sumar y restar hasta que al final hemos acabado.
Deje $L$ ser la colección de secuencias indexados por $\mathbb{N}$ tomando valores en $\mathbb{R}$.
$$L = \{ (x_0, x_1, x_2, \ldots ) : x_i \in \mathbb{R} \}$$
$L$ será un espacio vectorial con respecto a las componentes de la adición y la multiplicación escalar.
Definir un lineal mapa de $D$ $L$ por
$$L \ni x = (x_0, x_1, x_2, \ldots ) \quad\mapsto\quad Dx = (x_1, x_2, \ldots ) \in L$$
El resultado de la aplicación de $D - 1$ a una secuencia $x$ es la diferencia finita de $x$.
$$\left[ (D-1)x \right]_n = x_{n+1} - x_n$$
Si se aplican $(D-1)^k$ a la secuencia de $u = (n^k)_{n=0}^\infty$, usted encontrará
$$\left[ (D-1)^k u \right]_n = \sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j} \left[D^j u\right]_n = \sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j} u_{n+j} = \sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}(j+n)^k $$ Al $n = 0$, este es el lado izquierdo de la igualdad en la mano.
A ver en el lado izquierdo de la igualdad es, de hecho, igual a la RHS, puede utilizar el siguiente hecho:
Si $v$ es una secuencia cuyo valor es un polinomio en el índice de $n$, es decir, $$v_n = a_p n^p + a_{p-1} n^{p-1} + \cdots + a_0$$ para algunas constantes $a_p, a_{p-1},\ldots, a_0$, el de diferencia finita de $v$ será un polinomio en $n$ con grado uno menos. Además, el líder coeficiente se multiplica por un factor de $p$. es decir, $$\left[(D-1)v\right]_n = p a_p n^{p-1} + \cdots$$
Aplicar estos $k$ veces a la secuencia de $u = (n^k)_{n=0}^\infty$, encontrará $$\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}(j+n)^k = \left[ (D-1)^k u \right]_n = (D-1)^k n^k = k! n^0 = k!$$ que es una constante independiente de $n$ e igual a la RHS de la igualdad en la mano.
Yongyong
Puntos
303
Como lulu dijo, esto puede ser probado por medio de la inclusión-exclusión teorema. Tenemos \begin{equation} |\cup_{i=1}^k A_i|=\sum_{j=1}^k(-1)^{j+1}(\sum_{1\leq i_1<...<i_j\leq k}|A_{i_1}\cap...\cap A_{i_j}|). \end{equation} Ahora vamos a $A_i$ ser el subconjunto de la función de $[k]$ $[k]$tal que $i$ no es una imagen. A continuación, en el lado izquierdo de la ecuación es igual a $k^k-k!$, lo que significa que subtrct la bijective funciones de todas las funciones. El $j$-ésima componente del lado derecho es igual a $(-1)^{j+1}\begin{pmatrix}k\\j\end{pmatrix}(k-j)^k$, lo que significa que elegimos $j$ elementos que no son imágenes, y el $k$ elementos sólo tienen, a continuación, $k-j$ posibilidades para elegir una imagen. Ahora vamos a $\tilde{j}=k-j$, y la inserción de esta en la ecuación, usted encontrará la solución de la forma dada.
Más detalles: obtenemos entonces \begin{align} k^k-k!&=\sum_{j=0}^{k-1}(-1)^{k-j+1}\begin{pmatrix}k\\k-j\end{pmatrix}j^k\\ Y=-1\sum_{j=0}^{k-1}(-1)^{k-j}\begin{pmatrix}k\\j\end{pmatrix}j^k\\ Y=-1\sum_{j=1}^{k}(-1)^{k-j}\begin{pmatrix}k\\j\end{pmatrix}j^k+(-1)^{k-k}\begin{pmatrix}k\\k\end{pmatrix}k^k\\ Y=-1\sum_{j=1}^{k}(-1)^{k-j}\begin{pmatrix}k\\j\end{pmatrix}j^k+k^k. \end{align} Ambos lados subtrct $k^k$ y dividido por $-1$, se obtiene el resultado.
Anthony Shaw
Puntos
858
En esta respuesta, que se muestra para cualquier $l$, $$\begin{align} \sum_{r=0}^n\binom{n}{r}(-1)^r(l-r)^n &=\sum_{r=0}^n(-1)^{n-r}\binom{n}{r}(r-l)^n\\ &=n! \end {alinee el} $$ la identidad dada es esta identidad usando $l=0$.
Markus Scheuer
Puntos
16133
Aquí es una variante basada en el coeficiente de operador $[z^k]$ se usa para denotar el coeficiente de $z^k$ en una serie. De esta manera podemos escribir por ejemplo \begin{align*} [z^j](1+z)^k=\binom{k}{j}\qquad\qquad\text{or}\qquad\qquad k![z^k]e^{jz}=j^k \end{align*}
Obtenemos \begin{align*} \sum_{j=1}^k(-1)^{k-j}j^k\binom{k}{j} &=\sum_{j=0}^\infty(-1)^{k-j}k![z^k]e^{jz}[u^k](1+u)^k\tag{1}\\ &=(-1)^kk![z^k]\sum_{j=0}^{\infty}\left(-e^{z}\right)^j[u^k](1+u)^k\tag{2}\\ &=(-1)^kk^k\tag{3}\\ &=k![z^k]\left(z+\frac{z^2}{2!}+\frac{z^3}{3!}+\cdots\right)^k\tag{4}\\ &=k! \end{align*} y el reclamo de la siguiente manera.
Comentario:
En (1) se aplica el coeficiente de operador dos veces y extender el límite inferior y el límite superior de la serie sin cambiar nada, ya que sólo agregar ceros.
En (2) utilizamos la linealidad del coeficiente de operador y hacer algunos reordenamientos.
En (3) se utiliza la sustitución de la regla
\begin{align*} A(z)=\sum_{j=0}^\infty a_jz^j=\sum_{j=0}^\infty z^j [u^k]A(u) \end{align*}
- En (4) vemos que en cada una de las $k$ factores $(e^z-1)$ $z^1$ proporcionar una contribución a $z^k$.
