When $k < n$, what is the value of the sum $\sum_{j = 0}^{n}{n \choose j}(-1)^{j}(n - j)^k$?

Question

I know that when $k > n$, $$\sum_{j = 0}^{n}{n \choose j}(-1)^{j}(n - j)^k$$

counts the number of onto functions $f : [k] \rightarrow [n]$. But I have no clue what this sum is when $k < n$. Any hints?

Answer 1

The inclusion-exclusion reasoning that says that

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

is the number of functions from $[k]$ onto $[n]$ is valid whether or not $k\ge n$, so it constitutes a combinatorial argument that the sum must be $0$ when $k<n$. As an example, when $n=3$ and $k=2$ we have

$$\binom30\cdot3^2-\binom31\cdot2^2+\binom32\cdot1^2-\binom30\cdot0^2=9-12+3-0=0\;.$$