How many different ways are there to choose of $n$ subsets $\{i,j\},$ each of length $2,$ from $[2n]:= \{1,2,3,\ldots, 2n \}$?

Question

How many different ways are there to choose of $n$ subsets $\{i,j\},$ each of length $2,$ from $[2n]:= \{1,2,3,\ldots, 2n \}$ ? So for example for $n=25,\{ \{1,2\}, \{3,4\}, \{5,6\}, \ldots, \{49,50\} \} $ is one such way; $\{ \{1,50\}, \{2,49\}, \{3,48\}, \ldots, \{25,26\} \} $ is another.

My solution (for $n=50$) is this: Start with the set containing the number $n_1=1.$ There are $49$ numbers to choose from to pair up with $n_1:$ call this chosen number $n_2.$ Next, let $n_3$ be the least remaining number from $[2n]\setminus \{n_1,n_2\}.$ There are $47$ numbers we can choose to pair up with $n_3.$ Choose one and call it $n_4.$ Next, let $n_5$ be the least remaining number from $[2n]\setminus \{n_1,n_2, n_3,n_4\}.$ There are $45$ numbers we can choose to pair up with $n_5.$ Choose one and call it $n_6.$ And so on. We have found all possible different ways to choose $n$ subsets each of length $2,$ from $[2n],$ each way is done exactly once: this is due to the fact that $n_1<n_3<n_5<\ldots< n_{49};$ if for any $k,\ n_{2k+1}<n_{2k-1},$ then when $n_{2k-1}$ was chosen, it could have been chosen to be the number $n_{2k+1}<n_{2k-1},$ not $n_{2k-1},$ so $n_{2k-1}$ was not chosen to be the least remaining number from $[2n]\setminus \{n_1,n_2,\ldots n_{2k-2}\},$ a contradiction. So (by the product rule of counting) the solution is $49 \times 47 \times \ldots \times 3 \times 1.$

My questions are:

$(i)$ is my solution correct?

$(ii)$ is my solution missing any details or could the explanation be improved [in particular my explanation of uniqueness]? Do I need to mention PHP somewhere?

$(iii)$ are there any alternative solutions to this problem?

Answer 1

We can choose a pair $25$ times and then order them in $25!$ ways so the answer can also be counted as $\frac{\binom{50}{2} \cdot \binom{48}{2} \cdot … \cdot \binom{2}{2}}{25!}$ which is obviously equal to your answer:

$$\frac{\binom{50}{2} \cdot \binom{48}{2} \cdot … \cdot \binom{2}{2}}{25!}=\frac{(50/2 \cdot 49)\cdot(48/2 \cdot 47)\cdot … \cdot (2/2 \cdot 2)}{25!}=$$

$$=\frac{(49 \cdot 47\cdot … \cdot 1) \cdot 25!}{25!} = 49 \cdot 47\cdot … \cdot 1.$$

Answer 2

So we have a set with $2n$ distinct elements - $1$ through $2n$ - and we are to group these $2n$ elements into $n$ pairs.

If this is a correct understanding, here's a solution that should work.

Consider the $2n$ elements arranged in a row. The first two elements give us the first pair, the next two the second, and so on.

Now $2n$ elements can be arranged in $(2n)!$ ways.

Next, we need to account for some double counting.

Each pair can be arranged in $2$ ways. And the $n$ pairs can be arranged among themselves in $n!$ ways.

So the number of ways in we we can group the $2n$ distinct elements into pairs would be $$\frac{(2n)!}{2^n \cdot n!}$$

The same as your answer.$^{[1]}$

---

$^{[1]}$

$$\begin{align*} \frac{(2n)!}{2^n \cdot n!} &= \, \frac{2n \cdot 2n-1 \cdot 2n-2 \,\cdot \, ... \, \cdot \, 2 \cdot 1}{(2 \cdot n) \cdot (2 \cdot (n-1)) \,\cdot \, ... \, \cdot \, (2 \cdot 2) \cdot (2 \cdot 1)} \\[0.3cm] &= \, \frac{2n \cdot 2n-1 \cdot 2n-2 \,\cdot \, ... \, \cdot \, 2 \cdot 1}{(2n) \cdot (2n-2) \,\cdot \, ... \, \cdot \, 4 \cdot 2} \\[0.3cm] &= \, 2n-1 \cdot 2n-3 \,\cdot \, ... \, \cdot \, 3 \cdot 1 \end{align*}$$

Answer 3

Sketch of a proof by induction:

Suppose $2n-2$ numbers can be arranged in $(2n-3)\times(2n-5)\times\ldots\times 3\times 1$ ways.

Now add numbers $2n-1$ and $2n$. There are $2n-1$ choices for the partner of $2n$; this leaves us with $2n-2$ numbers, which by the inductive hypothesis can be allocated in $(2n-3)\times(2n-5)\times\ldots\times 3\times 1$ ways. So we get $(2n-1)\times\{(2n-3)\times(2n-5)\times\ldots\times 3\times 1\}$ as expected.