5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Isn't it just $k^n$? $\endgroup$ Commented Oct 5, 2013 at 15:52
  • 1
    $\begingroup$ Is it? I thought $k^n$ would be the case had those boxes been distinct. $\endgroup$ Commented Oct 5, 2013 at 15:54
  • $\begingroup$ Yes, you're right, I overlooked that. $\endgroup$ Commented Oct 5, 2013 at 17:07

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.