4

I don't understand something very simple at the beginning of the course in combinatorics. There are $2n$ students in class. They divide to couples to do homework.

How many such options of dividing there is ?

$$\frac{(2n)!}{2^n\cdot n!}$$

so $(2n)!$ are all the options, $n!$ is the different amount of ordering $n$ couples. Why and what is this $2^{n}$?

hardmath
  • 37,015
Ilya.K.
  • 1,288
  • 4
    Hint: the $2^n$ term arises because the pair $(A,B)$ is the same as the pair $(B,A)$. – lulu Oct 25 '15 at 16:24
  • 3
    It helps to do some small cases to be sure the formula makes sense, and possibly to get the insight for "what is this $2^n$" factor. – hardmath Oct 25 '15 at 16:25
  • 2
    Maybe it will help to do it another way. Imagine we have $8$ people. Line them up in order of student number, or alphabetically, or by height. The person on the left has $7$ choices of partner. For each such choice, the leftmost person not yet chosen has $5$ choices, and now the leftmost person not yet chosen has $3$ choices, for a total of $7\cdot 5\cdot 3$. – André Nicolas Oct 25 '15 at 16:33
  • Ok, first I want to try to understand the first method, as it mentioned as the formula. I took 2*2 students, and saw 12 options for arrangement in couples (each with anothe: $(12),(13)(14)(21)(23)(24)(31)(32)(34)(41)(42)(43)$. As lulu mentioned half of them repeating, so only 6 possible arrangements, and from them if I choose 2, the other choice is deterministic, it makes the answer 3 possible arrangements. Strange, First of all, I don't see manually the (2n)! options. The $2^{n}$ named as "internal arrangement" and the $n!$ arrangement. I still don't see clearly what the $2^{n}$ represent. – Ilya.K. Oct 25 '15 at 16:54

1 Answers1

14

One way to come up with a pairing of the students is to line them up in a row (there are $(2n)!$ ways to do this) and call the first two people the first team, the next two people the second team, and so on.

However, different ways of lining people up will lead to the same pairing into teams. We have to figure out how many lineups give the same pairing. Given one lineup, how could you change the lineup and still get the same teams? There are two things you can do.

One is go down the line, and have some of the paired-up people swap positions; for example, the line ABCDEFGH could become BACDEFHG. As there are $n$ pairs, each of whom you either swap or don't swap, there are $2^n$ ways to choose which pairs to swap.

The second thing you can do is move people in groups of 2, so the same people remain paired up and in the same order relative to each other. For example, if the line is ABCDEFGH, the pairs are. AB,CD,EF,GH so the line GHCDEFAB gives the same pairs. As there are $n$ pairs, you can reorder those pairs in $n!$ ways.

So every pairing arises from $2^nn!$ lineups of the $2n$ people. There are $(2n)!$ lineups, so the number of pairings is $\frac{(2n)!}{2^nn!}$.

In a more advanced course this would all be phrased in terms of counting orbits of a particular action of a hyperoctahedral group or a wreath product. But the above is really all that's going on.

Tad
  • 6,679
  • 1
    I don't understand why the answer isn't just (2n choose 2), since (n choose 2) is the number of ways groups of 2 can be chosen from n things. Or is that wrong? – travisjayday Oct 21 '19 at 04:45
  • @travisjayday because additional pairs are also being chosen. So it's like (2n choose 2) * (2n-2 choose 2) .. / n! (duplicates from order not mattering) – Learning stats by example Mar 19 '20 at 00:58