8
$\begingroup$

If you have $2n$ people how many different ways can you pair them up?

My method:

Considering making pairs like this:

Randomly line them up and then pair of the $1^{st}$ person in line with the $2^{nd}$, the $3^{rd}$ with the $4^{th}$, ..., the $(2n-1)^{th}$ with the $2n^{th}$

We have $2n!$ ways to line them up. However, this overcounts pairs, a lot.

Consider just 6 people. $A,B,C,D,E$ and $F$. The line $ABCDEF$ gives the same result as the line $BACDEF$

We can flip each person with their partner. He can do this $n$ times so we have overcounted $2^n$ times per order.

However, we have still overcounted! Consider again the line $ABCDEF$ this gives the same pairs as $ABEFCD$ We can indeed shuffle the pairs , as long as they remain with their partners in any order! We have $n!$ ways to shuffle the pairs.

My final answer is then $\frac{2n!}{2^n n!}$

Is this correct? Is anyone able to give some pointers as to how to use some code to confirm this? Does someone have a nicer answer?

$\endgroup$
3
  • 1
    $\begingroup$ Your question title says "Number of couples you can make", which is misleading and is not what the question asks. $\endgroup$
    – peterwhy
    Sep 1, 2021 at 10:56
  • 3
    $\begingroup$ You should write $(2n)!$. The usual meaning of $2n!$ is $2 \cdot (n!)$ $\endgroup$
    – jjagmath
    Sep 1, 2021 at 10:56
  • $\begingroup$ Note that $\frac{(2n)!}{2^nn!}=(2n-1)!!$ is the double factorial. $\endgroup$
    – robjohn
    Mar 23, 2023 at 18:19

3 Answers 3

6
$\begingroup$

Your answer is correct, but you should write it as $\frac{(2n)!}{2^n n!}$.

Other possible solution is the following. Take any person. Choose a couple for that person, that can be done in $2n-1$ ways. Take any of the remaining $2n-2$. Choose a couple for that person, that can be done in $2n-3$ ways. Continue this process until all couples are assigned. The total number of choices is $$(2n-1)(2n-3)\cdots 3\cdot 1 = \frac{(2n)(2n-1)(2n-2)\cdots 3\cdot 2\cdot 1}{(2n)(2n-2)\cdots2}=\frac{(2n)!}{2^n n!}$$

$\endgroup$
2
  • $\begingroup$ I know I'm late to the partyhere but I have a question regarding your second solution. Why is not relevant that there are 2n choices for the first person? In other words, why is a solution not: 2n * (2n-1) * (2n-3)....3*1. I'm also trying to make sense of the middle part of your equation, why are you dividing by 2n, 2n-2...etc? I get the sense my two questions are linked since they terms start to cancel out but it's not clear to me the logic there. $\endgroup$
    – Jackson
    Dec 20, 2023 at 1:01
  • $\begingroup$ I disagree with this choice of words: "Take any person". This implies that the first choice can be made among $2n$ people. A more precise argument goes like this. Number the people. Choose the lowest numbered person. Then choose that person's partner from the remaining people. Repeat until are pairs have been made. Essentially this means that we alternate between exactly one choice for the lowest numbered person and $2n$ minus the number of people remaining for the person's partner, i.e., $(1)(2n - 1)(1)(2n - 3)(1)(2n - 5) \cdots $. $\endgroup$ Feb 13 at 2:49
5
$\begingroup$

Your solution is correct (make sure to write $(2n)!$ instead of $2n!$). I'll give you another method, which I think is easier to understand.

Let $T(n)$ be the number of possible pairings of $2n$ people. If we take the fist person, it can be paired with $2n-1$ different people. Once you did this you have $2n-2$ people left, which proves that $T(n)=(2n-1)T(n-1)$. Now, it is trivially to show that $T(2)=1$.

Hence we have reduced the problem to a recurrence equation, wich is easy to solve and the solution is: $$T(n)=(2n-1)(2n-3)\dots 1=\frac{(2n)!}{2^n n!}$$

For me, and probably for many of us, transforming a combinatoric problem to a linear recurrence equation (which can be done in many of the exercises at undergad level) makes it easier, since it is more standard. In a harder problem, a solution like yours can be very difficult to find.

$\endgroup$
1
  • $\begingroup$ Thank you very much for this Marcos! $\endgroup$ Sep 1, 2021 at 11:30
3
$\begingroup$

Your reasoning is perfectly fine and your answer is correct.

Another approach is to use binomial coefficients (yet very parallel to your method).

  • How many ways are there to form the first couple? ${2n \choose 2}$.
  • The second couple? ${2n-2 \choose 2}$.
  • The third? ${2n-4 \choose 2}$.
  • etc.

Therefore, there are $${2n \choose 2} {2n-2 \choose 2} {2n-4 \choose 2} \dots {2 \choose 2} = \frac{(2n)!}{2^n}$$ ways to choose the couples (observe the cancellations in the product). Finally, as you argued above, the couples may be ordered in $n!$ ways. Hence, the final answer is $$\frac{(2n)!}{2^n n!}.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .