Prueba de una identidad combinada: $\sum \limits_{j=0}^n{(-1)^j{{n}\choose{j}}\left(1-\frac{j}{n}\right)^n}=\frac{n!}{n^n}$

Question

Quiero preguntar si hay una manera hábil de probar:

$$\sum_{j=0}^n{(-1)^j{{n}\choose{j}}\left(1-\frac{j}{n}\right)^n}=\frac{n!}{n^n}$$

Edit :

Sé que Yuval ha dado una prueba, pero esa no es directa. Solicito una prueba algebraica directa de esta identidad.

Gracias.

Answer 1

Se trata de la inclusión-exclusión para el recuento del número de mapas onto de $n$ a $n$ .

Answer 2

Esta respuesta es similar a la de Morón pero creo que es algo más sencilla. Ampliar $(e^x-1)^n$ utilizando el teorema del binomio para obtener $$(e^x-1)^n = \sum_{j=0}^n (-1)^{n-j} \binom{n}{j} e^{jx}.$$ Diferenciar ambos lados $n$ tiempos. Cada término del lado izquierdo contendrá un $e^x-1$ factor, excepto para un $n!e^{nx}$ y el lado derecho será $$\sum_{j=0}^n (-1)^{n-j} \binom{n}{j} j^n e^{jx}.$$ Entonces sustituye $x = 0$ para obtener $$n! = \sum_{j=0}^n (-1)^{n-j} \binom{n}{j} j^n.$$ Reindexar la suma y dividir por $n^n$ .

Answer 3

Comience con

$$\sum_{j=0}^{n} (-1)^j \binom{n}{j} (1+x)^{n-j} = x^n$$

que se deduce fácilmente del teorema del binomio.

Ahora diferencie, y multiplique por $\displaystyle (1+x)$ . Repite esto $\displaystyle n$ tiempos y establecer $\displaystyle x = 0$ .

Observa que el término constante del polinomio resultante en el lado derecho es $\displaystyle n!$ .

Se puede demostrar por inducción que el menor grado de $\displaystyle x$ que aparece en el lado derecho después de $\displaystyle k$ pasos ( $0 \lt \displaystyle k \le n$ ) es $\displaystyle x^{n-k}$ y tiene el coeficiente $\displaystyle n(n-1)\dots(n-k+1)$ .

Esto nos da el conjunto de identidades

$$\sum_{j=0}^{n} (-1)^j \binom{n}{j} (n-j)^{k} = 0, \ \ 0 \le k \lt n$$

$$\sum_{j=0}^{n} (-1)^j \binom{n}{j} (n-j)^{n} = n!$$

También me parece recordar que había una prueba que implicaba $\displaystyle \log x$ Si lo recuerdo, actualizaré esta respuesta más tarde.

Answer 4

Lema: Dejemos que $f(j) = \sum_{k=0}^n f_k j^k$ ser un grado $n$ polinomio. Afirmo que $\sum_{j=0}^{n} (-1)^j \binom{n}{j} f(j) = n! f_n$ .

Prueba: Para cualquier polinomio $g$ , defina $\Delta(g)$ para ser el polinomio $\Delta(g)(j) = g(j) - g(j+1)$ . Obsérvese que, si $g$ es un polinomio con término principal $a x^d + \cdots$ entonces $\Delta(g)$ es un polinomio con término principal $-d a x^{d-1} + \cdots$ . En particular, si $f$ es como en el enunciado del lema, entonces $\Delta^n(f)$ es la constante $(-1)^n n! f_n$ . La suma en cuestión es $\Delta^n(f)$ evaluado en $0$ . QED

Ahora, aplique el lema a $f(j) = (1-j/n)^n$ .

Answer 5

El resultado se deduce inmediatamente si se conocen los números Stirling del segundo tipo, y su significado combinatorio. Pero no es una prueba algebraica.

Actualización:

En la tabla 4 de estos Identidades combinatorias se afirma una identidad que -creo- es equivalente a la suya:

$ \displaystyle \sum_{k=0}^n (-1)^k {n \choose k} k^j = (-1)^n n!$

si $j=n$ (cero en caso contrario). Y sólo dice que se trata de un "Enunciado del teorema de las diferencias finitas de Euler" . No sé qué significa esto, y me gustaría saberlo.

Actualización 2:

En efecto, la identidad se desprende de la fórmula del n-ésima diferencia finita tomando la función $f(x)=x^j$