Prove using a combinatorial argument that $\frac{(2n)!}{2^n} \in \mathbb{N}$ Prove, using a combinatorial argument, that the numbers below are integers for any natural $n$: $$\frac{(2n)!}{2^n}$$
Attempt:
Suppose we organize a queue with $2n$ people, this can be done in $(2n)!$ ways. Now, from these possibilities, we take the pairing possibilities of each pair of people, for example, the first with the second, third with the fourth and etc... so we will have $$\frac{(2n)!}{2^n}$$ But since the order doesn't matter, we have $$\frac{(2n)!}{2^n\cdot n!}$$, which implies that $2^n|2n!$
I'm Right?
 A: You have $2n$ people and you are going to divide them into $n$ distinguishable pairs. This can be done on
$$\binom{2n}{2,2,2,\ldots,2}=\frac{(2n)!}{2!2!2!\ldots 2!}=\frac{(2n)!}{2^n}$$ ways. You can derive this formula by these two ways:

*

*First you arrange them in a row of length $2n$ on $(2n)!$ ways. Then you make pairs: first with second, third with fourth and so on. Then you observe that changing two people in a pair doesn't change the pair but both these arrangements participated in the initial arrangement in a row. There you have to divide the number by $2^n$.

*You choose the first pair on $\binom{2n}2$ ways. Next on $\binom{2n-2}{2}$ ways, and so on. Then you have
$$\binom{2n}2\cdot \binom{2n-2}2\cdots \binom{4}2\cdot \binom{2}2 = \frac{(2n)!}{2^n}$$  ways.

A: *

*Line up $2n$ people in $(2n)!$ ways,

*Take out two at a time serially to get $n$ pairs

*Two ways to assign a leader from each such pair

This represents $\dfrac{(2n)!}{2^n}$, and obviously must be an integer for  $n \in N$
