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.
Best Answer
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.