How many ways are there to distribute 5 balls into 3 boxes, under additional conditions? How many ways are there to distribute 5 balls into 3 boxes if:


*

*both the boxes and balls are labeled

*the balls are labeled but the boxes are not

*the balls are unlabeled but the boxes are labeled

*both the balls and boxes are unlabeled
My way of doing these is as follows:


*

*$3^5$?

*$C(5,5)$?

*$3!5! - C(5,5)$?

*$C(3,5)$?
Where $C(k,n)$ means $\binom{n}{k}$.
 A: 1) Your answer is correct; for each ball, you can choose any box, and every choice is distinguishable at any time.
2) You want to distribute your 5 distinguishable balls into 3 indistinguishable boxes. Let $B(5,3)$ denote the number of ways in which this can be done into exactly 3 indistinguishable non-empty boxes, and use the recurrence relation $B(n,k)=B(n-1,k-1)+kB(n-1,k)$ with $B(n,1)=1$ and $B(n,n)=1$. You seek $B(5,1)+B(5,2)+B(5,3)$. For further reference, see Stirling number.
3) You want to separate your 5 indistinguishable balls into 3 distinguishable boxes. Note that every admissible separation uniquely corresponds to a permutation of the string $XXbbbbb$.
4) You want to partition your 5 indistinguishable balls into 3 indistinguishable boxes. Let $p(5,3)$ denote the number of ways in which this can be done into exactly 3 indistinguishable non-empty boxes, and use the recurrence relation $p(n,k)=p(n-1,k-1)+p(n-k,k)$ with $p(n,1)=1$ and $p(n,n)=1$. You seek $p(5,1)+p(5,2)+p(5,3)$. For further reference, see partition.
A: (2) Since the boxes are indistinguishable, there are 5 different cases for arrangements of the number of balls in each box: $(5,0,0)$, $(4,1,0)$, $(3,2,0)$, $(3,1,1)$, or $(2,2,1)$. 
$(5,0,0)$: There is only $1$ way to put all 5 balls in one box.
$(4,1,0)$: There are $\binom{5}{4} = 5$ choices for the 4 balls in one of the boxes.
$(3,2,0)$: There are $\binom{5}{3} = 10$ choices for the 3 balls in one of the boxes.
$(3,1,1)$: There are $\binom{5}{3} = 10$ choices for the 3 balls in one of the boxes, and we simply split the last two among the other indistinguishable boxes.
$(2,2,1)$:  There are $\binom{5}{2} = 10$ options for one of the boxes with two balls, then $\binom{3}{2} = 3$ options for the second box with two balls, and one option remaining for the third.  However since the boxes with two balls are indistinguishable, we are counting each pair of balls twice, and must divide by two.  So there are $\dfrac{10 \times 3}{2} = 15$ arrangements of balls as $(2,2,1)$.
Thus the total number of arrangements for 3 indistinguishable boxes and 5 distinguishable balls is $1 + 5 + 10 + 10 + 15 = \boxed{41}$.
$\textbf{Alternate solution:}$ There are $3^5 = 243$ arrangements to put 5 distinguishable balls in 3 distinguishable boxes.  Among these 243 arrangements, there is one case in our problem that is counted three times: if all 5 balls are placed in one box and the other two boxes both contain nothing.  This leaves 240 other arrangements.
For every other case, the contents of each box is different, and so these cases are each counted $3! = 6$ times.  Therefore there must be 40 of these cases, and we have $\boxed{41}$ cases total.
