Combinatoric Explanation of General Identity When $k \lt n$, what is the value of the sum $$\sum\limits_{j=0}^n {n \choose j}(-1)^j (n-j)^k.$$ Explain combinatorially.
Any ideas on where to start?
 A: This is inclusion-exclusion principle.
Consider the functions from a set $S$ with $k$ elements to a set $T$ with $n$ elements.
Let $A_j$ be the functions whose range excludes a fixed subset of $j$ elements.
The sum is 
$$
\sum_{j=0}^n (-1)^j \binom{n}{j}|A_j|.$$
Then the sum represents the number of all onto functions from $S$ to $T$. (Inclusion-exclusion principle)
Since $k<n$, this number is clearly zero.
Also, there is an analytic proof of this. 
Consider the function 
$$f(x)=\sum_{j=0}^n\binom{n}{j}(-1)^je^{(n-j)x} = (e^x -1)^n$$
Then the sum represents, the $k$-th derivative of $f$ at 0, say $f^{(k)}(0)$. Since $k<n$, this also gives zero.  
A: The sum vanishes. It counts the ordered partitions of $k$ elements into $n$  nonempty subsets, and there are none for $k\lt n$. This is $\displaystyle n!\left\{k\atop n\right\}$, where $\displaystyle\left\{k\atop n\right\}$ is a Stirling number of the second kind.
A: As I explained in this other answer, you can recognise the alternating sum along row $n$ of Pascal's triangle, with the index (here $j$) used as a shift in the remaining expression (here $(n-j)^k$), as an application of the $n$-th power of the finite difference operator $-\Delta:f\mapsto(x\mapsto f(x)-f(x+1))$, and this operator decreases the degree of polynomial functions by $1$, making all those of degree less than $n$ identically zero. Here one has, from the fact that $(-\Delta)^n(f)=0$ when $f(x)=x^k$, that
$$
  \sum_{i=0}^n(-1)^i\binom ni (x+i)^k = 0\qquad\text{for all $x\in\mathbf C$, if $k<n$.}
$$
Now taking $x=-n$ it easily follows that the summation in the question vanishes.
As for a combinatorial interpretation for the summation, one that comes to mind is a signed summation over all ways to forbid a subset of $j$ out of $n$ elements, and choose a map from a $k$-set to the remaining elements (an element may be not-forbidden but still not in the image of the map), with the sign being given by the partity of the number of forbidden elements. Since $k<n$, no map from a $k$-set to a $n$-set can be surjective; one can take the first element not in the image and flip its "forbidded status", and this gives a sign-reversing involution on the set, so the signed sum is $0$.
