¿Prueba de la suma de $n!=\sum_{k=0}^n \binom{n}{k}(n-k+1)^n(-1)^k$?

Question

Iba a través de una teoría del número del libro el otro día y encontrado esta pregunta. Pregunta para la prueba de la siguiente ecuación:

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

Traté de duro pero no podía entender cómo empezar. ¿Alguien podría dar la prueba? ¡Gracias de antemano!

Answer 1

Deje $A=\{1,2,\ldots, n\}$. El número de bijective funciones de $f:A\to A$ es claramente $n!$.
Por otro lado, el número de funciones de $A$ a un conjunto con $n-k+1$ elementos es $(n-k+1)^n$ e hay $\binom{n}{k}$ formas para elegir un subconjunto de a $A$ $n-k$ elementos.
Así que la fórmula sigue directamente de la inclusión-exclusión principio.

Otra posibilidad es utilizar el avance operador diferencia $\delta$ traer un polinomio $p(x)$$p(x+1)-p(x)$. Si $p$ no es una constante, tenemos que el grado de $\delta p$ es el grado de $p$ menos uno, y el primer término de $\delta p$ es igual a la líder plazo de $p'$. De ello se desprende que $\delta^n$ que se aplica a $p(x)=x^n$ da la constante de $n!$ cualquier $x$ , $(\delta^{n}p)(1)$ la suma.

Answer 2

Tenga en cuenta que, por conmutatividad, $$\sum_{k=0}^{n}\dbinom{n}{k}\left(n-k+1\right)^{n}\left(-1\right)^{k}=\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{n}\left(-1\right)^{n-k} $$ so let us consider $$\sum_{k=0}^{n}\dbinom{n}{k}x^{k+1}\left(-1\right)^{n-k}=x\left(x-1\right)^{n} $$ then if we differentiate and we multiply by $x$ we get $$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)x^{k+1}\left(-1\right)^{n-k}=nx^{2}\left(x-1\right)^{n-1}+x\left(x-1\right)^{n} $$ and if we repeat the process $$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{2}x^{k+1}\left(-1\right)^{n-k}=n\left(n-1\right)x^{3}\left(x-1\right)^{n-2}+2x^{2}n\left(x-1\right)^{n-1}+nx^{2}\left(x-1\right)^{n-1}+x\left(x-1\right)^{n} $$ and so if we repeat the process $n$ times we get $$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{n}x^{k+1}\left(-1\right)^{n-k}=n!x^{n}+\textrm{sumandos con una potencia positiva de }\left(x-1\right) $$ so if we evaluate the sum at $x=1$ obtenemos

$$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{n}\left(-1\right)^{n-k}=\color{red}{n!} $$

como quería.

Answer 3

Otra variación del tema. En el siguiente utilizamos el coeficiente de operador $[z^k]$ para denotar el coeficiente de $z^k$ en una serie. De esta manera podemos escribir por ejemplo \begin{align*} \binom{n}{k}=[z^k](1+z)^n\qquad\text{and}\qquad k^n=n![z^n]e^{kz} \end{align*}

Obtenemos \begin{align*} \sum_{k=0}^n&\binom{n}{k}(n-k+1)^n(-1)^k\\ &=\sum_{k=0}^n\binom{n}{k}(k+1)^n(-1)^{n-k}\tag{1}\\ &=\sum_{k=0}^\infty[z^k](1+z)^nn![x^n]e^{(k+1)x}(-1)^{n-k}\tag{2}\\ &=(-1)^nn![x^n]e^x\sum_{k=0}^\infty(-e^x)^k[z^k](1+z)^n\tag{3}\\ &=(-1)^nn![x^n]e^x\left(1-e^x\right)^n\tag{4}\\ &=(-1)^nn![x^n]\left(-x\right)^n\tag{5}\\ &=n!\\ \end{align*} y el reclamo de la siguiente manera.

Comentario:

• En (1) podemos intercambiar el orden de la suma de $k\rightarrow n-k$

• En (2) se amplía el límite para infty sin cambiar nada, ya que estamos añadiendo ceros sólo. Aplicamos el coeficiente de operador $\binom{n}{k}$$(k+1)^n$$e^{(k+1)x}$.

• En (3) hacemos un simple reordenamiento

• En (4), usamos la sustitución de la regla de que el coeficiente deoperador \begin{align*} A(x)=\sum_{k=0}^\infty a_k x^k=\sum_{k=0}^\infty x^k [z^k]A(z) \end{align*}

• En (5) tenemos en cuenta la expansión de la serie \begin{align*} e^x(1-e^x)^n&=(1+x+\cdots)\left(-x+\frac{x^2}{2}-\cdots\right)^n\\ &=\left((-x)^n\pm\text{powers of }x\text{ greater than }n\cdots\right) \end{align*} y sólo necesitan respetar la $x$plazo con una potencia igual a $n$.

Answer 4

Supongamos que buscamos para evaluar

$$\sum_{k=0}^n {n\choose k} (-1)^k (n-k+1)^n.$$

Introducir

$$(n-k+1)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n-k+1)z) \; dz.$$

Llegamos por la suma

$$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n+1)z) \sum_{k=0}^n {n\elegir k} (-1)^k \exp(-kz) \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n+1)z) (1-\exp(-z))^n \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(z) (\exp(z)-1)^n \; dz.$$

Esto es $$n! [z^n] \exp(z) (\exp(z)-1)^n.$$

Ahora $$\exp(z)-1 = z + \frac{z^2}{2} + \frac{z^3}{6} +\cdots$$ y por lo tanto

$$(\exp(z)-1)^n = z^n + \cdots.$$

Por lo tanto, el resultado es

$$n! [z^0] \exp(z) = n!.$$