What is the number of ways of dividing $2n$ distinct balls into $n$ identical bins, such that each bin contains two balls?
My working was as follows:
First select $n$ balls in $\binom{2n}{n}$ ways, then put one ball into each bin, and arrange it in a total of $n!$ possible ways, then, put the rest of the $n$ balls into the $n$ bins, in one way. This can be done in a total of $\binom{2n}{n} n!$ ways. But there seems to be double counting for each bin, so we need to divide by $2^{n}$ to get the correct answer, i.e, $\binom{2n}{n} \frac{n!}{2^n} $.
My question is how is this double counting happening?
Also, more generally, is there a way to determine how to divide $kn$ distinct balls into $n$ identical bins such that each bin has $k$ balls?
Best Answer
Since the bins are identical, the question essentially reduces to - in how many ways can $2n$ distinct balls be divided into $n$ pairs?
Let's line up the balls in a row. The first two balls make one pair, the next two another pair, and so on. Consider any one arrangement. There are $n$ pairs and they can be arranged among themselves in $n!$ ways. Also, the two balls in each pair can be arranged in 2 ways (so $2^n$ ways for $n$ pairs). That means for each unique grouping, there are $2^n \cdot n!$ arrangements.
Now, $2n$ distinct balls can be arranged among themselves in a row in $(2n)!$ ways.
So the number of unique groupings is $\dfrac{(2n)!}{n! \cdot 2^n}$.
Generalizing the above solution, the required number would be $\dfrac{(kn)!}{n! \cdot (k!)^n}$.