3
$\begingroup$

I've been thinking about this problem which I think is interesting, but can't solve it.

There are $n$ distinguishable items, and $b$ distinguishable bins. Each bin has to include at least one item. But, once some set of items are placed in a bin, they become indistinguishable. How many ways are there to place the items into the bins?

(1) The condition that each bin has to include at least one item can be resolved by simply tweaking the problem a bit: suppose there are $n-b$ items, and proceed. So this is not a big hurdle. (Or, it can be, depending on how we handle the second condition below.)

(2) The second condition that the items in a bin are indistinguishable is a bit tricky. Suppose we have 3 items, and 2 bins. The items are numbered as 1, 2 and 3. The bins are denoted as A and B.

The second condition says that, we have to consider the following as identical: A - 1, B - 2, 3. vs. A - 1, B - 3, 2.

However, we have to consider the following as distinct: A - 1, B - 2, 3 vs. A - 2, 3, B - 1.

How can I compute the total number of ways to place the items into the bins?

Thanks.

$\endgroup$
3
$\begingroup$

Your second condition is implicit in the usual notion of bin in combinatorics: there is no imposed ordering among the items inside the bin (which is unrelated to the possibility to distinguish the items among each other). So you are just asking for the number of surjective maps from the set of your $n$ items to the set of $b$ bins.

This is one of the problems of the twelvefold way. Its answer is given by $b!{n\atopwithdelims\{\}b}$, where $n\atopwithdelims\{\}b$ is a Stirling number of the second kind. The factor $b!$ can be understood by the fact that their nonempty contents allow distinguishing the $b$ bins even if we forget their labels; the action of the group of permutations of the bins partitions the set of solutions (surjective maps) into orbits of $b!$ each.

$\endgroup$
2
$\begingroup$

The number of functions from $n$ items to $b$ bins is $b^n$

The number of functions from $n$ items to $b$ bins that miss a particular $k$ bins is $(b-k)^n$. There are $\binom{b}{k}$ ways to choose the $k$ bins to miss.

Thus, inclusion-exclusion says that the number of surjective functions from $n$ items to $b$ bins is $$ \sum_{k=0}^b(-1)^k\binom{b}{k}(b-k)^n $$ which agrees with Eric Thoma's answer except when $n=0$:

  • Eric Thoma's answer gives $0$ for $b=0$ (empty sum) and $(-1)^{b-1}$ when $b\gt0$.

  • This answer gives $1$ for $b=0$ and $0$ for $b\gt0$.

$\endgroup$
1
$\begingroup$

First lets not have the restriction that all the bins are nonempty. There are $b$ choices of bins for each ball, and so there are $b^n$ different configurations.

How many configurations are we counting that we should not? Lets leave one bin empty. There are $b$ choices for the empty bin, and $(b-1)^n$ ways to fill the rest.

Now we are overcounting configurations with two empty bins. This is the principle of inclusion exclusion.

We see the total number of configurations is $$ \sum_{i=0}^{b-1} (-1)^{i} {b \choose i}(b-i)^n. $$

Disclaimer: I haven't numerically checked this so I would not be surprised if I am in error.

$\endgroup$
  • $\begingroup$ For $n\gt0$, this is correct since $(b-b)^n=0$. However, for $n=0$, $(b-b)^n=1$ (using the definition $0^0=1$) $\endgroup$ – robjohn Dec 28 '15 at 11:00

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.