How many ways are there to distribute 5 balls into 7 boxes if each box must have at most one in it if:

a) both the boxes and balls are labeled

b) the balls are labeled but the boxes are not

c) the balls are unlabeled but the boxes are labeled

d) both the balls and boxes are unlabeled

Can someone give me a general approach to problems like the one above? What happens in the four different cases that makes them completely different? Why does "indistinguishable" or "distinguishable" determine how the problem can be approached?

  • 2
    $\begingroup$ I don't understand the meta-questions. The four cases are different because "distinguishable" and "indistinguishable" are different. $\endgroup$ – Qiaochu Yuan Nov 14 '12 at 1:40

Let's try to break up each parts into subpart:

a) Balls and boxes are labeled, so $1111100\neq 1100111$ where $1$ is a filled box and $0$ an empty one, and $12345\neq12435$ where I labeled each ball.

i) subpart 1: Choose which ball you want to fill. They all contain exactly one ball.

ii) The problem is now a standard permutation problem

b) Boxes aren't labeled so there really is just one way to do this, putting $5$ balls into $5$ bins.

c) Balls are not labeled here, so this is part a) minus ii). Just choose which bin to fill

d) Same as b), not much to be done here.

Now to answer you question more precisely, let us look at a broader example. Imagine I have $4$ balls and $3$ bins, but no restriction on the number of balls each bin can hold.

If both are labeled, then just pick a bin for each balls. This give $3^4$ ways since each ball can go in any of the $3$ box.

If Balls are unlabeled both boxes are différent, then this is classic Stars and bars counting technique.

The harder part comes when boxes are unlabeled. First if the balls are labeled then there are $4$ ways the ball can be distributed, namely $$ \{\{4,0,0\},\{3,1,0\},\{2,2,0\},\{1,1,2\}\} $$ Now $\{4,0,0\}$ has only $1$ possible configuration and $\{3,1,0\}$ has $4$, i.e. choose the ball that is alone in its bin. The remaining two situations each have $6$ possible configurations, that is choose $2$ balls to be together from the $4$, the others being set depending on a $1-1$ configuration or $2-0$. This gives a total of $15$ configurations.

In general, this is given by Bell number. If boxes can't be empty, you'll want to look up Stirling number of the second kind.

If everything is unlabeled, then this is given (in general, $n$ balls into $k$ non-empty bins) by the number of $k$-element partitions of $n$


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.