# Distribution of distinct balls in identical boxes

how can I derive a formula for the number of distributions of $n$ different balls in $k$ identical boxes. Where $\mathbf{empty\ box}$ is allowed.

I know this is equivalent to finding the number of ways to partition a set of $n$ labelled (distinct) objects into $k\ \mathbf{non\ empty}$ unlabelled subsets, which is basically ${n\brace k}$ (stirling number of the $2^{nd}$ kind).

But the problem is, ${n\brace k}$ doesn't allow $\mathbf{empty}$ partitions, where as my problems does.

• Isn't it just $k^n$? – Raskolnikov Oct 5 '13 at 15:52
• Is it? I thought $k^n$ would be the case had those boxes been distinct. – dibyendu Oct 5 '13 at 15:54
• Yes, you're right, I overlooked that. – Raskolnikov Oct 5 '13 at 17:07

I believe you'll find it's $$\sum_{m=1}^k {n\brace m}$$ Note that I am taking ${n\brace m}=0$ when $m>n$.
Why? How many ways can you fill $m$ identical boxes with $n$ distinct balls such that each box has at least one ball? Now, clearly there must be some number of boxes filled, let that be $m$. $m$ can be anything from 1 to $k$, but if $k>n$, then obviously you can't fill all the boxes, and thus no combination requiring filling of all boxes matters.