# 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.

-
If you have access to Knuth's Fundamental algorithms, Stirling numbers are extensively discussed there. Also, have you read the Wikipedia article? –  Harald Hanche-Olsen Feb 6 '13 at 8:54
I'm afraid I don't. Could you send me a link? –  Hagrid Feb 6 '13 at 8:57
See here and here‌​. –  Brian M. Scott Feb 6 '13 at 8:58
Fundamental algorithms is not online, as far as I know. Any halfway decent university library ought to have it. –  Harald Hanche-Olsen Feb 6 '13 at 8:59
It’s this book. –  Brian M. Scott Feb 6 '13 at 8:59

$\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.

-