0

Combinatorial proof of $\frac{(2n)!}{2^n \times n!} \in \mathbb{N}$

My try: Suppose there are $n$ families $F1,F2,F3,..Fn$ containing couples(Wife and Husband pair). So there are total $2n$ people.

We have $P=(2n)!$ as number of ways to arrange them in a line.

Now what is the combinatorial significance of $2^n \times n!$?

My thought is this:

Let there are $n$ different rooms. Each room should be accommodated with one person and no two rooms contain same family members. Thus first room can be occupied in $2$ ways, say from family $F1$ with either of Husband or Wife.Second room can also be occupied in $2$ ways say from $F2$ and so on. So total $2^n$ ways and these people can be arranged in $n!$ ways. Hence total $$Q=2^n \times n!$$

Any way to proceed from here to say the ratio $\frac{P}{Q}$ is an integer?

Ekaveera Gouribhatla
  • 13,026
  • 3
  • 34
  • 70
  • Say the two members of any given family are identical. In that case, you could indeed arrange them in a line in $\frac{(2n)!}{2^n}$ ways in a line. Think of one more restriction that would allow you to divide by $n!$. – Nothing special May 09 '23 at 06:28
  • Consider the following restrictions in deciding what counts as an arrangement: (1) The order of husbands of the family doesn't matter i.e., $H_2W_2H_1W_1$ is same as $H_1W_2H_2W_1$. (2) If you swap the positions of $H_i$ and $W_i$ of the same family $F_i$, it's still counted as same arrangement. With these restrictions in place, there are $\frac{(2n)!}{2^n\times n!}$ arrangements. – Nothing special May 09 '23 at 06:43

2 Answers2

4

$\displaystyle \frac{(2n)!}{2^n \times n!}~$ happens to be the answer to the following problem:

How many distinct ways are there of forming $~n~$ pairs from $~2n~$ people, selecting the pairs without replacement, where the order that the pairs are formed is deemed irrelevant.

Therefore, the expression has to be an integer.

One (inelegant) way of verifying the answer is to consider the equivalent expression:

$$\frac{1}{n!} \times \left[ ~\binom{2n}{2} \times \binom{2n-2}{2} \times \cdots \times \binom{4}{2} \times \binom{2}{2} ~\right]. \tag1 $$

In (1) above, the RHS represents forming the first pair, from $~2n~$ people, then forming the next pair, and the next, and so on.

In (1) above, the LHS represents the over-counting adjustment factor needed to compensate for the fact that there are $~n!~$ ways of ordering the formation of any specific (i.e. distinct) group of $~n~$ pairs.

user2661923
  • 35,619
  • 3
  • 17
  • 39
1

Alternately, the no. of fixed point free involutions in the symmetric group of order $2n$ is exactly $\frac{(2n)!}{n!\times 2^n}$.

An involution is a permutation $\sigma$ such that $\sigma \circ \sigma =i$. A fixed point free involution is one that has no $k$ such that $\sigma(k)=k$ for any $0<k\le 2n$.

This can be seen using the formula for the size of the conjugacy class in the symmetric group given by $\frac{n!}{\prod_{r}r^{n_r}n_r!}$ where $n_r$ is the no. of cycles of size $r$.

The exponential generating function of the fixed point free involutions can also be seen, combinatorially, as $\def\textsc#1{\dosc#1\csod}\def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\textsc{CYC}_{=2}(\mathcal{Z}))$ which is $e^{\frac{x^2}{2}}$.

Umesh Shankar
  • 2,787