0
$\begingroup$

The problem is to count the number of ways to distribute $n$ distinguishable balls in $k$ boxes, where $k-s$ boxes are indistinguishable between each other and the remaining boxes $k - (k-s)$ are indistinguishable between each other.

For example we need to distribute 3 balls

{Ball#1, Ball#2, Ball#3}

in 4 boxes

{RedBox, RedBox, BlueBox, BlueBox}

The two red boxes are indistinguishable from each other, and the two blue boxes are indistinguishable from each other as well.

Would love any idea suggestions on how to think about or solve this problem!

$\endgroup$

1 Answer 1

1
$\begingroup$

The number of ways of distributing $n$ labelled balls amongst $k$ unlabelled boxes is $\sum_{i=0}^k{n\brace i}$, where $n\brace i$ is a Stirling number of the second kind. If we put $m$ balls into the $s$ boxes of the one type and the rest into the $k-s$ boxes of the other type, we can do this in

$$\binom{n}m\left(\sum_{i=0}^s{m\brace i}\right)\left(\sum_{i=0}^{k-s}{{n-m}\brace i}\right)=\binom{n}m\sum_{i=0}^s\sum_{j=0}^{k-s}{m\brace i}{{n-m}\brace j}\;,$$

and the desired number is therefore

$$\begin{align*} \sum_{m=0}^n\sum_{i=0}^s\sum_{j=0}^{k-s}\binom{n}m{m\brace i}{{n-m}\brace j}&=\sum_{i=0}^s\sum_{j=0}^{k-s}\sum_{m=0}^n{m\brace i}{{n-m}\brace j}\binom{n}m\\\\ &=\sum_{i=0}^s\sum_{j=0}^{k-s}{n\brace{i+j}}\binom{i+j}i\;.\tag{1} \end{align*}$$

In your toy example, for instance, this becomes

$$\begin{align*} \sum_{i=0}^2\sum_{j=0}^2{3\brace{i+j}}\binom{i+j}i&=\sum_{j=0}^2{3\brace j}\binom{j}0+\sum_{j=0}^2{3\brace{j+1}}\binom{j+1}1+\sum_{j=0}^2{3\brace{j+2}}\binom{j+2}2\\ &=(0+1+3)+(1+6+3)+(3+3+0)\\ &=20\;, \end{align*}$$

which is easily verified independently. I don’t know whether $(1)$ can be significantly simplified; I don’t see anything at the moment, but perhaps someone will have a better idea.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .