Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
I don't understand the meta-questions. The four cases are different because "distinguishable" and "indistinguishable" are different. –  Qiaochu Yuan Nov 14 '12 at 1:40

1 Answer 1

up vote 5 down vote accepted

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.