Podría alguien explicarme donde estas dos fórmulas vienen de las aplicaciones del teorema del binomio? $$\sum_{k=0}^n {n \choose k}(-1)^kk^r=0$$ para enteros no negativos $r\lt n$. Y $$\sum_{k=0}^n {n \choose k}(-1)^kk^n=(-1)^nn!$$
Respuestas
¿Demasiados anuncios?
DiGi
Puntos
1925
Ellos no vienen de el teorema del binomio: vienen de la inclusión-exclusión principio. Esto es más fácil de ver si los multiplicamos por $(-1)^n$ para obtener
$$\sum_{k=0}^n\binom{n}k(-1)^{n-k}k^r=\begin{cases} 0,&\text{if }r<n\\ n!,&\text{if }r=n\;. \end{casos}$$
El lado izquierdo de la cuenta surjections de$[r]=\{1,\ldots,r\}$$[n]=\{1,\ldots,n\}$. Por supuesto, esto es $0$ al $r<n$ $n!$ al $r=n$.
El lado izquierdo puede escribirse como sigue:
$$\begin{align*} \sum_{k=0}^n\binom{n}k(-1)^{n-k}k^r&=\sum_{k=0}^n\binom{n}{n-k}(-1)^{n-k}k^r\\ &=\sum_{k=0}^n\binom{n}k(-1)^k(n-k)^r\\ &=n^r-\binom{n}1(n-1)^r+\binom{n}2(n-2)^r-+\ldots\;. \end{align*}$$
El primer término, $n^r$, es el número de funciones de$[r]$$[n]$. Para cada una de las $k\in[n]$ hay $(n-1)^r$ funciones de$[r]$$[n]\setminus\{k\}$, y $n$ opciones posibles para $k$; restando $\binom{n}1(n-1)^r$ lanza estos no surjective funciones de$[r]$$[n]$. Sin embargo, las funciones cuyos rangos de perder (al menos) dos elementos de $[n]$ son arrojados fuera de (al menos) dos veces y se añade de nuevo, dando
$$n^r-\binom{n}1(n-1)^r+\binom{n}2(n-2)^r\;.$$
Este es ahora un sobre cuenta, ya que las funciones cuyos rangos de perder (al menos) tres elementos de $[n]$ ya han sido contados una sola vez, eliminado tres veces, y contó tres veces: en la red que han sido contados una sola vez y la necesidad de ser arrojado a la basura otra vez.
La inclusión-exclusión principio asegura que el pleno de la suma correctamente cuentas por todo y por lo tanto, realmente no dar el número de surjections de$[r]$$[n]$.
Zilin J.
Puntos
2617
Una Prueba Usando El Teorema Del Binomio:
Podemos demostrar por inducción.
El teorema del binomio dice $$(x-1)^n = \sum_{k}{n\choose k}(-1)^{n-k} x^k.$$ Setting $x=1$ gives a proof for $r=0$. Suppose the statement is true for $<r$.
Supongamos $r\leq n$. Tome $r$th derivado de la fórmula anterior, obtenemos $$\begin{eqnarray}n(n-1)\ldots (n-r+1)(x-1)^{n-r} &=& \sum_{k}{n\choose k}(-1)^{n-k}k(k-1)\ldots (k-r+1)x^{k-r}\\ &=& \sum_{k}{n\choose k}(-1)^{n-k}P(k)x^{k-r},\end{eqnarray}$$ where $P(k)=k^r+$ lower terms. Set $x=1$. By the induction hypothesis, the terms evaluated by the lower terms sum to $0$, and so RHS $=\sum_k{n\elegir k}(-1)^{n-k}k^r$. If $r < n$, then LHS $=0$. If $r=n$, then LHS $=n!$. Esto completa la prueba.
Comentario: Una mancha de la manera de demostrarlo es contar el número de surjections de$[r]$$[n]$. Por la inclusión-exclusión principio, obtenemos el número de surjections igual a $$\sum_k {n\choose k}(-1)^{n-k}k^r.$$ However, when $r<n$, there are no surjections, whereas, when $r=n$, there are $n!$ muchos.
Anthony Shaw
Puntos
858
Considere la posibilidad de $\binom{k}{j}$ grado $k$ polinómica (combinatoria polinomio) en $k$: $$ \binom{k}{j}=\frac{k(k-1)(k-2)\cdots(k-j+1)}{j!}\la etiqueta{1} $$ No es difícil ver que podemos escribir cualquier polinomio de grado $m$ como suma de combinatoria de los polinomios de grado $m$ o menos. En particular, hemos $$ \newcommand{\stirtwo}[2]{\left\{{#1}\cima{#2}\right\}} k^m=\sum_{j=0}^mj!\stirtwo{m}{j}\binom{k}{j}\etiqueta{2} $$ donde $\stirtwo{m}{j}$ es un Número de Stirling del Segundo Tipo.
Desde $k^m$ puede ser escrita como una suma de combinatoria de los polinomios de grado $m$ o menos, $$ n\gt m\implica\stirtwo{m}{n}=0\etiqueta{3} $$ Además, dado que el coeficiente de $k^m$$m!\binom{k}{m}$$1$, $$ \stirtwo{m}{m}=1\etiqueta{4} $$ El uso de $(2)$ en la suma de los rendimientos $$ \begin{align} \sum_{k=0}^n\binom{n}{k}(-1)^kk^m &=\sum_{k=0}^n\binom{n}{k}(-1)^k\sum_{j=0}^mj!\stirtwo{m}{j}\binom{k}{j}\\ &=\sum_{j=0}^mj!\stirtwo{m}{j}\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{k}{j}\\ &=\sum_{j=0}^mj!\stirtwo{m}{j}\sum_{k=0}^n(-1)^k\binom{n}{j}\binom{n-j}{k-j}\\ &=\sum_{j=0}^mj!\stirtwo{m}{j}\binom{n}{j}(-1)^j(1-1)^{n-j}\\ &=(-1)^nn!\stirtwo{m}{n}\tag{5} \end{align} $$ Equtions $(3)$, $(4)$, y $(5)$ dar los resultados que se buscan.
GmonC
Puntos
114
En lugar de tratar de interpretar esto como una aplicación directa de la fórmula binominal, creo que es mejor reconocer las sumas de la forma $\sum_k(-1)^k\binom nkf(x+k)$ o $\sum_k(-1)^k\binom nkf(x-k)$ como viene de la repetición de las diferencias finitas de $f$. En tu ejemplo es $f(x)=x^r$ fijos $0\leq r\leq n$, tomado con el tiempo, a $x=0$. Sin embargo, esto también se da en diferentes formas en esta pregunta y otro y uno similar a este (y tal vez en otros que no he logrado encontrar).
En el espacio de las funciones definidas en entero (o entero no negativo) de los argumentos, definir el avance operador diferencia $\Delta$ por $$ \Delta(f)=\bigl(x\mapsto f(x+1)-f(x)\bigr) \qquad \text{para cualquier $f:\Bbb Z\to\Bbb R$} $$ Entonces uno ya ha $\Delta=S-I$ donde $S$ es el operador de desplazamiento a la $f\mapsto\bigl(x\mapsto f(x+1)\bigr)$ $I$ es la identidad de $f\mapsto \bigl(x\mapsto f(x)\bigr)=f$; ya que estos operadores conmutan se puede aplicar la fórmula binomial para obtener $$ \Delta^n(f) = \sum_{k=0}^n\binom nk(-I)^{n-k}S^k(f) = \left(x\mapsto \sum_{k=0}^n(-1)^{n-k}\binom nkf(x+k) \right) . $$ Para el propósito del reconocimiento es útil tener una variante donde el exponente de $-1$ coincide con el menor índice en el coeficiente binomial: $$ \sum_{k=0}^n(-1)^k\binom nkf(x+k) = (-1)^n\Delta^n(f)(x) $$
Ahora, el punto que hace que sea fácil de calcular en ciertas situaciones, como la de la pregunta, es que $\Delta$ reduce el grado de funciones polinómicas, matando constante, y se multiplica el coeficiente inicial por el grado como de diferenciación. Esto significa que con $f:x\mapsto x^r$ $0\leq r\leq n$ ha $\Delta^n(f)=(x\mapsto 0)$ al $r<n$, mientras que $\Delta^n(f)=(x\mapsto n!)$ al $r=n$. Esto le da a su dos ecuaciones.
