# Stirling numbers, binomial coefficients

Could you help me prove the following:

$$\left\{n\atop k\right\} = \frac{1}{k!} \cdot \sum^{k}_{j=0} {k\choose j} \cdot j^{n} \cdot (-1)^{k-j}$$

It looks very scary to me. I've looked for it in Graham, Knuth, Patashnik's "Concrete Mathematics", but I didn't find it. All I know about Stirling numbers is that we can use them as coefficients in $x^{(n)(n-1)...(n-k+1)}$ in the sum of $x^k, \ 0 \le k \le n$

or in $x^n$ when we want to express it as a sum of $x^{(n)(n-1)...(n-k+1)}$. But I don't think this would help me in any way.

I think we divide the sum on the left hand side by $k!$ because when we choose subsets order doesn't matter. Then maybe ${k\choose j}$ means that we choose $j$ elements to our $k$ -element subset and we can choose them in $j^n$ (?) ways and $(-1)^{k-j}$ must mean inclusion\exclusion principle.

$\left\{n\atop k\right\}$ is the number of ways of putting $n$ distinguishable objects into exactly $k$ indistinguishable boxes. If we give the boxes identities, they can be permuted in $k!$ ways, so $\sum_{j\ge 0}\binom{k}jj^n(-1)^{k-j}$ ought to be the number of ways of putting $n$ distinguishable objects into $k$ distinguishable boxes subject to the condition that no box be empty. In other words, it should be the number of surjections from $[n]$ to $[k]$, and indeed it is, by a straightfoward inclusion-exclusion argument.