Part (a) How many ways are there to put $4$ balls into $3$ boxes, given that the balls can all be distinguished and so can the boxes? (For instance, perhaps each ball is a different color, and each box is a different color as well.)
Part(b) How many ways are there to put $4$ balls into $3$ boxes, given that the balls can all be distinguished but the boxes are not distinguished? (Thus, for example, putting all the balls in the first box is counted as the same outcome as putting all the balls in the second box.)
Part (c) How many ways are there to put $4$ balls into $3$ boxes, given that the balls are not distinguished but the boxes are?
I know that there are 4 possible arrangments for Part (a):
4 0 0,
2 2 0,
2 1 1,
3 1 0. I counted the number of combinations of each of these and got 15, but that is incorrect. I'm not sure what I did wrong and I don't know how to do Part (b) or Part (c). Any help is appreciated.
Best Answer
$\blacksquare$ For part (a), [I've explained at the end why you were getting a wrong answer]
for each of the balls $O_1, O_2, O_3, O_4$ (distinguishable, hence we can assign names like this) you have $3$ options $Box_1, Box_2, Box_3$ for them to go in, and the placement of $O_1$ (or $O_2$, or $O_3$, or $O_4$) does not depend or affect the placement of any of the other balls, that is to say, these are independent choices, so we can multiply their options as $3\times 3\times 3\times 3=81$
$\blacksquare$ For part (b),
you have $4$ distinguishable balls $A,B,C,D$ and the problem is equivalent to finding the number of partitions of the set $Balls=\{A,B,C,D\}$ into at most $3$ disjoint subsets. You have the following partitions of the number $4$ as sums $$1+1+2, \ 2+2, \ 3+1,\ 4$$ and for each of these partitions, you have to find the number of ways in which the set $Balls$ can be broken up. As you have mentioned, there is ${4\choose 4}=1$ $\textbf{[for the partition $4=4$]}$ only one way of putting all the balls together. There are $\frac1{2!}{4\choose 2}{4-2 \choose 2}=3$ $\textbf{[for the partition $4=2+2$]}$ ways of pairing up the balls in two boxes (which are indistinguishable), ${4\choose 3}{4-3 \choose 1}=4$ $\textbf{[for the partition $4=3+1$]}$ ways of putting $3$ balls together in one box and $1$ ball in another box and ${4\choose 2}{4-2\choose 1}{4-2-1\choose 1}\frac1{2!}=6$ $\textbf{[for the partition $4=2+1+1$]}$ ways to put $2$ balls together in one box, and the remaining two separately in different boxes.
The way the counting has been done here is, say for the $4=2+1+1$ partition, you need to choose $2$ balls from $Balls$ to account for the first $2$, which can be done in ${4\choose 2}$ ways, now you have $4-2$ balls remaining, and you must choose $1$ from there to account for the first $1$ in the partition above, which you can do in ${4-2\choose 1}$ ways, and similarly the last ball can be chosen from the remaining ${4-2-1}$ balls in ${4-2-1\choose 1}$ way. Of course, writing the last term in these products is redundant, because once we have chosen all the remaining groupings for the partitions, there is only one ball remaining for us to choose which can obviously be done in $1$ way only. Finally we divide by $2!$ to account for the overcounting that we have due to summands of the same magnitude, i.e. $\{AB, C, D\}, \ \{AB, D, C\}$ are the same.
So, you add up all these numbers to get $6+4+3+1=14$ for part (b). Counting the partitions like this gets tough as you might figure, so check out Stirling numbers of the second kind which count just the answer to this problem when you feel comfortable.
$\blacksquare$ For part (c),
Since the balls are not distinguishable but the boxes are, let's say we place $x$, $y$, $z$ balls in the $1^{st},\ 2^{nd}, \ 3^{rd}$ boxes respectively. We have then, the following restrictions on $x,y,z$ which have to be integers, by the way: $$x,y,z \ge 0; \\ x+y+z=4$$ i.e. we have to find the number of non-negative integral solutions to the above equation $x+y+z=4$. Counting that number is same as counting the number of ways in which you can arrange $4$ balls and $2$ '+' signs in a line, because each such arrangement will lead to each unique solution triplet $(x,y,z)$ $$\text{ like } \blacklozenge + \blacklozenge \blacklozenge \blacklozenge + \text{ denotes the solution } 1+3+0 \\ \text{ and } ++\blacklozenge \blacklozenge \blacklozenge \blacklozenge \text{ denotes the solution } 0+0+4$$ So we have to count the number of permutations of $6$ symbols where $4$ are alike of one kind and $2$ are alike of another kind, and the number of ways to do that is $\dfrac{6!}{4!2!}=15$.
Finally, to answer why you were getting a wrong answer for part (a), you actually considered the balls as indistinguishable (do you see why?), and the boxes as distinguishable [which was the case for part (c)] and hence $15$ is the answer for part (c).