En $k \lt n$ ¿cuál es el valor de la suma $$\sum\limits_{j=0}^n {n \choose j}(-1)^j (n-j)^k.$$ Explícalo combinatoriamente.
¿Alguna idea sobre por dónde empezar?
Respuestas
¿Demasiados anuncios?
Krzysztof Hasiński
Puntos
229
Se trata del principio de inclusión-exclusión.
Consideremos las funciones de un conjunto $S$ con $k$ elementos a un conjunto $T$ con $n$ elementos. Sea $A_j$ son las funciones cuyo ámbito excluye un subconjunto fijo de $j$ elementos. La suma es $$ \sum_{j=0}^n (-1)^j \binom{n}{j}|A_j|.$$
Entonces la suma representa el número de todas las funciones onto de $S$ a $T$ . (Principio de inclusión-exclusión)
Desde $k<n$ este número es claramente cero.
Además, existe una prueba analítica de ello. Consideremos la función $$f(x)=\sum_{j=0}^n\binom{n}{j}(-1)^je^{(n-j)x} = (e^x -1)^n$$ Entonces la suma representa, el $k$ -ésima derivada de $f$ a 0, digamos $f^{(k)}(0)$ . Desde $k<n$ esto también da cero.
JiminyCricket
Puntos
143
La suma desaparece. Cuenta las particiones ordenadas de $k$ elementos en $n$ subconjuntos no vacíos, y no hay ninguno para $k\lt n$ . Esto es $\displaystyle n!\left\{k\atop n\right\}$ donde $\displaystyle\left\{k\atop n\right\}$ es un Número de Stirling del segundo tipo .
GmonC
Puntos
114
Como expliqué en esta otra respuesta se puede reconocer la suma alternada a lo largo de la fila $n$ del triángulo de Pascal, con el índice (aquí $j$ ) utilizado como desplazamiento en la expresión restante (aquí $(n-j)^k$ ), como aplicación del $n$ -enésima potencia del operador de diferencias finitas $-\Delta:f\mapsto(x\mapsto f(x)-f(x+1))$ y este operador disminuye el grado de las funciones polinómicas en $1$ haciendo que todos los de grado inferior a $n$ idénticamente cero. Aquí se tiene, a partir del hecho de que $(-\Delta)^n(f)=0$ cuando $f(x)=x^k$ que $$ \sum_{i=0}^n(-1)^i\binom ni (x+i)^k = 0\qquad\text{for all $ x\in\mathbf C $, if $ k<n $.} $$ Ahora tomando $x=-n$ se deduce fácilmente que la suma en la pregunta desaparece.
En cuanto a una interpretación combinatoria de la suma, se me ocurre una suma con signo sobre todas las formas de prohibir un subconjunto de $j$ de $n$ y elija un mapa de $k$ -a los elementos restantes (un elemento puede no estar prohibido pero no estar en la imagen del mapa), con el signo dado por la partición del número de elementos prohibidos. Dado que $k<n$ no hay mapa de a $k$ -set to a $n$ -puede ser suryectiva; se puede tomar el primer elemento que no está en la imagen y darle la vuelta a su "estado de prohibición", y esto da una involución de signo inverso en el conjunto, por lo que la suma con signo es $0$ .
