factorial como la diferencia de poderes: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?

Question

Las sucesivas diferencia de potencias de números enteros conduce a factorial de ese poder.

Creo que esta es la fórmula

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

Pero he encontrado ninguna prueba en internet.

Por favor, dame una prueba para ella. Es para cualquier valor de $l$ satisface ?

Edit: Por la Respuesta de abajo, aquí $l$ debería haber sido $n$, cosa que es falsa.

Answer 1

Deje $A:=\{ x_1,..,x_n \}$$B=\{y_1,..,y_m \}$.

Permite contar el número de a las funciones de $f:A \to B$. Hay $m^n$ funciones de$A$$B$. Permite contar ahora las que no lo están en:

Definir

$$P_i= \{ f : A \to B |y_i \notin f(A) \}$$

A continuación, tenemos que averiguar la cardinalidad de a $\cup_i P_i$.

Por la inclusión principio de exclusión de

$$|P_1 \copa P_2 ..\copa P_m |=\sum |P_i|-\sum |P_i \cap P_j|+\sum |P_i \cap P_j \cap P_k| -... \\=\binom{m}{1}(m-1)^n-\binom{m}{2}(m-2)^n+\binom{m}{3}(m-3)^n-... $$

Por lo tanto, en total hay

$$m^n-\binom{m}{1}(m-1)^n+\binom{m}{2}(m-2)^n-\binom{m}{3}(m-3)^n-...=\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n$$

Cuando $n=m$ el número de en funciones es

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

Pero cualquier función de $f: \{ x_1,..,x_n \} \to\{y_1,..,y_n \}$ es sobre si y sólo si es un bijection. Por lo tanto el número de en funciones es igual al número de bijections, que es $n!$.

Por lo tanto

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

Answer 2

Esta identidad también tiene una prueba algebraica. Supongamos que la suma que estamos tratando de evaluar está dada por $$\sum_{k=0}^n {n\choose k} (-1)^k (n-k)^{n}.$$

Observar que cuando multiplicamos dos exponenciales funciones de generación de las secuencias de $\{a_n\}$ $\{b_n\}$ obtenemos que \begin{align} A(z) B(z) &= \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ &= \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!} \end{align} es decir, el producto de las dos funciones de generación es la generación de la función de $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Ahora, en el presente caso es evidente que se han $$A(z) = \sum_{q\ge 0} (-1)^q \frac{z^q}{q!} = \exp(-z).$$ Además, hemos $A$B(z) = \sum_{q\ge 1} p^{n} \frac{z^p}{q!} = \exp(z) \sum_{k=1}^{n} {n\llave k} z^k,$$ como puede ser visto por inducción. Para $n=1$ hemos $$B_1(z) = \sum_{q\ge 1} p \frac{z^p}{q!} = z \sum_{q\ge 1} \frac{z^{p-1}}{(p-1)!} = \exp(z)\times z.$$ Ahora usando la hipótesis de inducción tenemos $$B_{n+1}(z) = z \frac{d}{dz} B_n(z) = z \exp(z) \sum_{k=1}^{n} {n\llave k} k z^{k-1} + z \exp(z) \sum_{k=1}^{n} {n\llave k} z^k.$$ Este es \begin{align} & z \exp(z) \sum_{k=0}^{n-1} {n\brace k+1} (k+1) z^k + z \exp(z) \sum_{k=1}^{n} {n\brace k} z^k \\ &= z \exp(z) \left({n\brace 1} + \sum_{k=1}^{n-1} \left({n\brace k+1} (k+1)+{n\brace k}\right)z^k+ {n\brace n} z^{n}\right) \\ &= z \exp(z) \left({n+1\brace 1} + \sum_{k=1}^{n-1} {n+1\brace k+1} z^k + {n+1\brace n+1} z^{n}\right) \\ &= \exp(z) \left({n+1\brace 1} z + \sum_{k=1}^{n-1} {n+1\brace k+1} z^{k+1} + {n+1\brace n+1} z^{n+1}\right) = \exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k. \end{align}

Volviendo al problema original nos encontramos con que la suma tiene el valor $$n! [z^n] A(z) B_n(z) = n! [z^n] \sum_{k=1}^{n} {n\llave k} z^k = n! {n\llave n} = n!$$ que iba a ser mostrado.

Un ejercicio útil en el álgebra de los números de Stirling y los coeficientes binomiales. Aquí es un MSE enlace que apunta a otra cálculo del mismo tipo.

Adenda. En respuesta a la observación que podemos, de hecho, muestran que $$\sum_{k=0}^n {n\choose k} (-1)^k (l-k)^{n}$$ para $l$ un entero.

Observar que $$l-k = (n-k)+(l-n)$$ and put $p=l-n.$ Utilizando la misma configuración que antes de ahora han \begin{align} B(z) &= \sum_{q\ge 0} (q+p)^n \frac{z^q}{q!} = \sum_{q\ge 0} \sum_{m=0}^n {n\choose m} q^m p^{n-m} \frac{z^q}{q!} \\ &= \sum_{q\ge 0} p^n \frac{z^q}{q!} + \sum_{q\ge 0} \sum_{m=1}^n {n\choose m} q^m p^{n-m} \frac{z^q}{q!} = \exp(z) p^n +\sum_{m=1}^n {n\choose m} p^{n-m} \sum_{q\ge 0} q^m \frac{z^q}{q!} \\ &= \exp(z) p^n + \exp(z) \sum_{m=1}^n {n\choose m} p^{n-m} \sum_{k=1}^m {m\brace k} z^k. \end{align} Esta fórmula también se aplica a las $p=0$ si asumimos que $0^0=1$, en cuyo caso se produce la primera fórmula se deriva de la anterior. De ello se sigue que $$n! [z^n] A(z) B_n(z) = n! [z^n] \left(p^n+\sum_{m=1}^n {n\elegir m} p^{n-m} \sum_{k=1}^m {m\llave k} z^k\right) = n! {n\elegir n} {n\llave n} = n!$$ mostrando así el resultado para todos los $l.$

Answer 3

En esta respuesta son tres pruebas diferentes de esta cancelación lema: $$ \sum_{j=k}^n(-1)^{n-j}\binom{n}{j}\binom{j}{k} =\left\{\begin{array}{} 1&\text{if }n=k\\ 0&\text{otherwise} \end{array}\right.\la etiqueta{1} $$ Inductivamente, podemos ver que cualquier polinomio en $j$ grado $m$ puede escribirse de forma única como $$ \sum_{k=0}^mc_k\binom{j}{k}\etiqueta{2} $$ donde el coeficiente de $j^m$$\dfrac{c_m}{m!}$.

Poner a $(1)$$(2)$,$m\le n$, tenemos $$ \begin{align} \sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}\sum_{k=0}^mc_k\binom{j}{k} &=\sum_{k=0}^m\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}\binom{j}{k}\\ &=c_n\tag{3} \end{align} $$ Si $m\lt n$,$c_n=0$. Si $m=n$, $c_n$ $n!$ multiplicado por el coeficiente de $j^n$.

---

La aplicación de $(3)$ $$ \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!\tag{4} \end{align} $$ porque, para cualquier $l$, $(r-l)^n$ es un grado $n$ polinomio en $r$ en el que el coeficiente de $r^n$$1$.

Answer 4

Utilizando la definición de la Exponencial de la Serie,

$$e^x=\sum_{0\le r<\infty}\frac{x^r}{r!} \implies e^x-1=x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots$$

Tomando $n$th poder, $$ (e^x-1)^n=\left(x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots\right)^n$$

$$\text{Now, }(e^x-1)^n=e^{nx}-\binom n1e^{(n-1)x}+\binom n2e^{(n-2)x}-\cdots$$

$$=\sum_{0\le r<\infty}\frac{(nx)^r}{r!}-\binom n1\sum_{0\le r<\infty}\frac{\{(n-1)x\}^r}{r!}+\binom n2\sum_{0\le r<\infty}\frac{\{(n-2)x\}^r}{r!}-\cdots$$

Así, el coeficiente de $x^r$ $(e^x-1)^n$

$$\frac{n^r}{r!}-\binom n1\frac{(n-1)^r}{r!}+\binom n2\frac{(n-2)^r}{r!}-\cdots$$

$$\text{ Again, } \left(x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots\right)^n=x^n+\text{ the higher powers of } x$$

Igualando obtenemos

$$\frac{n^r}{r!}-\binom n1\frac{(n-1)^r}{r!}+\binom n2\frac{(n-2)^r}{r!}-\cdots=\begin{cases} 0 &\mbox{if } 0\le r< n \\ 1 & \mbox{if } r=n \end{casos} $$

Answer 5

Supongamos que estamos tratando de evaluar $$\sum_{q=0}^n {n\choose q} (-1)^q (k-q)^n.$$ Observar que $$(k-q)^n = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((k-q)z) \; dz.$$

Esto da por la suma de la integral $$\frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{q=0}^n {n\elegir q} (-1)^q \exp((k-q)z) \; dz \\ = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{\exp(kz)}{z^{n+1}} \sum_{q=0}^n {n\elegir q} (-1)^q \exp(-qz) \; dz \\ = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{\exp(kz)}{z^{n+1}} (1-\exp(-z))^n \; dz.$$

Observar que $$1-\exp(-z) = z-\frac{1}{2}z^2+\frac{1}{6}z^3-\cdots$$ por lo $(1-\exp(-z))^n$ comienza a $z^n$, lo que significa que el residuo es un (a$\exp(kz)$ comienza a $z^0$), dando a $$n!$$ como el resultado final.