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.

  • $\begingroup$ Isn't it just $k^n$? $\endgroup$ Oct 5 '13 at 15:52
  • 1
    $\begingroup$ Is it? I thought $k^n$ would be the case had those boxes been distinct. $\endgroup$
    – dibyendu
    Oct 5 '13 at 15:54
  • $\begingroup$ Yes, you're right, I overlooked that. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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