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$ – Raskolnikov 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$ – 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.


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.