Help with deriving solution for multiple birthday problem

Question

I've been thinking about one version of the more general birthday problem, namely for the case of k $\ge$ 3. I found this document explaining the solution through a combinatorial method, but I'm having trouble understanding the following line in its "Solution for k=3" section:

$$\frac{1}{i!}\cdot{2i \choose 2}\cdot{2i-2 \choose 2}\cdot{2i-4 \choose 2}\cdot { } _{\dots}\cdot{4 \choose 2} = \frac{(2i)!}{i!\cdot2^i} = \left[ \prod_{j=1}^{i} 2j-1 \right]$$

The author explains that the above represents the number of different ways of arranging each selection of 2i people into sets of two.

I believe I understand the purpose of the binomial terms, since if there are 5 pairs (for example) of double birthdays, then first there are 10 (2$\cdot$5) people in total who belong in the group of people with double birthdays, from whom we choose 2. After that there still remains 8 people, from whom we choose 2 more. And so on, until the final ${4 \choose 2}$ term.

However, I fail to understand the purpose of the $\frac{1}{i!}$ factor. I suspect it has something to do with accounting for the redundancy introduced when counting this way, as mentioned on page 8 of this paper (which I also don't fully understand tbh).

Please help me understand this.

Answer 1

Yes, it is to correct for redundancy. Here is the reason why $$ \binom{2i}{2}\cdot \binom{2(i-1)}2\cdots\cdot\binom22 $$ does not represent the number of ways to pair of $2i$ people.

Let us look at $i=3$. There are six people, numbered $1$ to $6$. The expression is $$ \binom62\cdot \binom42\cdot \binom22 $$ which means, "choose two people out of six, then choose two people from the remaining four people, then choose two people from the remaining two." One way to follow these instructions would be to choose

1. $\{2,4\},$ for the first pair,
2. $\{1,5\}$ for the second pair,
3. $\{3,6\}$ for the third pair.

Here is a different way to follow the instructions.

1. $\{1,5\}$ for the first pair,
2. $\{2,4\},$ for the second pair,
3. $\{3,6\}$ for the third pair.

These are the exact same pairings; we just listed their names in a different order. This is why you need to divide by $i!$; when you group all of lists which are permutations of each other, each group will have $i!$ members, so you divide the total number of lists by $i!$ to get the total number of groups.