Finding number of ways to put four balls in k bins

Question

I'm trying to calculate how many ways we can put four indistinguishable balls in n indistinguishable bins, given that the maximum each bin can hold is r balls.

Answer 1

If both the balls and bins are indistinguishable, then with sufficiently many bins, it doesn't matter which bins have balls in them. For instance, if we arrange the bins in a line, and place balls in them, you can reorder the bins by decreasing number of balls. The only way to distinguish the bins and balls is to count how many balls are in a bin.

With this in mind, for $n \ge 4$, there are three distinct arrangements:

1. Each of the balls is in a different bin.
2. Two balls are in different bins, and the remaining two balls are together in a third bin.
3. Two balls are in one bin, and the other two balls are in a different bin.

There are no other arrangements with a maximum limit of two balls per bin.

If $n \le 3$, then we need to consider each case:

1. If $n = 1$, no arrangements are possible.
2. If $n = 2$, then there is only one arrangement--two balls per bin.
3. If $n = 3$, then there are two arrangements--two balls per bin, or one ball in each of two bins, and two balls in the third.

So the answer is $\min(n-1, 3)$ for all positive integer $n$.

---

But I don't think that indistinguishable bins is what was intended. The question is much more interesting if the bins are distinguishable. To this end, suppose each ball goes in a distinct bin. Then the number of such configurations is simply $\binom{n}{4}$, since we are picking four of the $n$ bins to place the balls.

Now consider the case where two balls go into one bin, and the remaining two balls go into distinct bins. So there are three distinct bins, and from the previous reasoning, $\binom{n}{3}$ ways to choose those bins. Then there are $3$ ways to pick which of those bins gets the additional ball, so the number of such outcomes is $3 \binom{n}{3}$.

Finally, consider the case where two balls go into each of two distinct bins. We can do this in $\binom{n}{2}$ ways. Unlike the previous case, there is no multiplicative factor because once the two bins are chosen, each one must be given two balls, and the balls are indistinguishable.