1

Suppose there are $2n$ students, then how many ways there are to arrange them to $n$ different pairs?

I saw the solution but it doesn't help me to finally understand it. I'll be happy if someone can visualize it to me (e.g with a tree for $n=3$).

Thanks!

Answer is:

enter image description here

Arthur
  • 199,419
MXO120
  • 117
  • What was the solution you saw? Did you just see the final answer, or was there a reasoning that you didn't quite understand? – Arthur May 08 '23 at 08:54
  • Edited the thread with the answer. I do not see the relation between the calculation to the problem, like, why do we decrease by 2 each choice and why it ends up as subsets calculating – MXO120 May 08 '23 at 09:02
  • 1
    Consider what happens when $~n=3.~$ There are $~\displaystyle \binom{6}{2}~$ ways of forming the first pair. Then, once the first pair is formed, there are $~\displaystyle \binom{4}{2}~$ ways of forming the second pair. Finally, there are then $~\displaystyle \binom{2}{2}~$ ways of forming the third pair. Further, you must apply the over-counting adjustment factor of $~\dfrac{1}{3!}~$ to compensate for the fact that the same group of $~3~$ pairs can be formed in $~3!~$ ways, since that is the number of ways that the $~3~$ pairs can be ordered. – user2661923 May 08 '23 at 09:05
  • @Arthur Simpler for whom? The point of my comment was not to provide an answer but to stretch the intuition of the OP (i.e. original poster). In my opinion, my comment represents the first basic group of insights that I would want the new Combinatorics student to be confronted with. You have to crawl before you can walk. – user2661923 May 08 '23 at 09:09

2 Answers2

2

The left-side part of the answer is the easiest to explain, in my opinion.

Line up all the people in a line. Take the first person, and pair them up with someone. There are $2n-1$ options. Take these two people out of the line. Take the next person in the line and pair them up with someone. There are $2n-3$ options. Rinse and repeat until there are no more people left. The total number of options for pairing people up this way is therefore $$ (2n-1)(2n-3)\cdots 3\cdot1 $$ often notated as $(2n-1)!!$, using the so-called double factorial.

Arthur
  • 199,419
2

Line the $2n$ students up and pick $n$ of them, which is $\binom{2n}{n}$. Then take the remaining students, rearrange them $n!$ ways and assign them to the chosen students. Remove duplicate pairs by dividing by $2^n$.

JMP
  • 21,771
  • It mostly made me understand the exact part which I struggle to understand and hence try to visualize - why do we divide by 2^n and not 2? – MXO120 May 08 '23 at 09:44
  • 1
    @MXO120; if an arrangement is say $(12)(34)(56)$ (so $n=3$), there are three pairs that can be reversed (e.g. $(21(34)(65)$, so we divide by $2^3=8$. – JMP May 08 '23 at 09:47
  • Oh 2^3 comes from (2!)^3. Now I see the big picture, thanks! – MXO120 May 08 '23 at 09:51
  • @MXO120; yes, as in number of arrangements of $aabbcc$ where the letters don't matter. – JMP May 08 '23 at 11:20