Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Please, help.

share|improve this question
    
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
show 7 more comments

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.