Prove using a combinatorial argument that $\frac{(2n)!}{2^n} \in \mathbb{N}$

Question

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?

Answer 1

• 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$

Answer 2

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.