How many ways can 26 letters be divided into 13 pairs?

Question

The question is: a plug board has 26 letters, and there are 13 cables. The cables connect all possible pair of letters.

How many possible configurations does the plug board provide? In other words, how many ways can 26 letters be divided into 13 pairs?

The result I found by calculation and some logic is:

$$25\cdot 23\cdot 21\cdot 19\cdot 17\cdot 15\cdot 13\cdot 11\cdot 9\cdot 7\cdot 5\cdot 3 = 7 905 853 580 625.$$

Is this correct?

How is the mathematical algorithm and formula to calculate this and similar problems?

Answer 1

One way to count would be as follows.

Consider the letters ordered, and labeled as $1,2,3,4,\dots,2N$. Let $A(N)$ be the number of possibilities to "pair them in $N$ pairs". We take the first letter, $1$, and pair it, i.e. we count its possible pairings. There are $(2N-1)$ possibilities. We make a choice of the $1$-match, eliminate this pair from the list, reorder, and count again.

In this way we get inductively: $$ A(2N)=(2N-1)A(2N-2)\ . $$ Because $A(2)=1$, we get the formula $A(2N)=(2N-1)(2N-3)\cdots5\cdot 3\cdot 1$.

(Some people call this number $(2N-1)!!$.)

(It is hard to put the hands on the "similar problems" part of the question.)

Answer 2

Yes, you are correct. This is my approach: we select a set of $13$ letters among the $26$ in $\binom{26}{13}$ ways. Then we assign the remaining $13$ letters to the chosen letters in $13!$ ways. Finally we divide the result by $2$, $13$ times because we are not interested in the order of the letters in the $13$ couples. The final result is $$\frac{\binom{26}{13}\cdot 13!}{2^{13}}=\frac {26!}{2^{13} \cdot 13!}=7 905 853 580 625$$ which is the same of yours.

Answer 3

Another approach is: the first pair can be selected in ${26\choose 2}$ ways, but we are not interested in the position of the pair among the $13$ pairs, hence we divide it by ${13\choose 1}$: $$\frac{{26\choose 2}}{{13\choose 1}}$$ Similarly, for other pairs.

At the end we get: $$\frac{{26\choose 2}}{{13\choose 1}}\cdot \frac{{24\choose 2}}{{12\choose 1}}\cdot\frac{{22\choose 2}}{{11\choose 1}}\cdot\frac{{20\choose 2}}{{10\choose 1}}\cdot \frac{{18\choose 2}}{{9\choose 1}}\cdot\frac{{16\choose 2}}{{8\choose 1}}\cdot\frac{{14\choose 2}}{{7\choose 1}}\cdot\frac{{12\choose 2}}{{6\choose 1}}\cdot\frac{{10\choose 2}}{{5\choose 1}}\cdot\frac{{8\choose 2}}{{4\choose 1}}\cdot\frac{{6\choose 2}}{{3\choose 1}}\cdot\frac{{4\choose 2}}{{2\choose 1}}\cdot\frac{{2\choose 2}}{{1\choose 1}},$$ which is what you have.