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?
Best Answer
Let's try to break up each parts into subpart:
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.
1a. Choose which box you want to fill. They all contain exactly one ball.
1b. The problem is now a standard permutation problem
Boxes aren't labeled so there really is just one way to do this, putting $5$ balls into $5$ bins.
Balls are not labeled here, so this is part a) minus ii). Just choose which bin to fill
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$