Counting problem

Question

There are exactly 20 students currently enrolled in a class. How many different ways are there to pair up the 20 students, so that each student is paired with one other student? Solve this in at least 2 different ways.

My attempt: first is using combinations, C(20, 2) * C(18, 2) * C(16, 2) * ... * C(2, 2), then divided it by 10!.

second solution: 10!

But they seems to have different values, so which one is correct? I need 2 methods.

Answer 1

Your approach and intuition for the first method are correct and give a solution of 654729075 ways. Let's look at a different way to do it.

We can use the following strategy to pair up students: line all of the students up and make the first two students a pair, then make the next two students a pair, and so on.

How many different ways are there to line up n students? There are n! different ways. However, some of these ways give repeated pairs. We can think of this using a smaller value of n. Let's say that n=4 and we have 4 students named A, B, C, and D.

Both ABCD and CDAB are ways to line up the students, but they end up with A and B paired and C and D paired, so they have the same pairing. The issue here is that we have the same pairings, but the pairs are ordered differently. We don't want to double count here. With n students, there will be n/2 pairs, so there are (n/2)! ways to order those pairs. To avoid double counting, we will divide by (n/2)!.

Also, both ABCD and BACD are valid ways to line up the students, but both ways give A and B paired and C and D paired. We also don't want to double count situations where the pairings are the same, but a pair is swapped in order (AB vs. BA). With n/2 pairs, there are 2^(n/2) ways to choose which pairs to swap, so we would like to divide by that, too.

Let's now look at the problem with n=20. The formula we get is (20!) / (10! * 2^10). Plugging this into a calculator gives 654729075 once again.

Answer 2

Any one of 20 students can be paired with any one of the 19 students remaining to be chosen.

Then write 20 × 19 or 380 and remember that "Mike can be paired with Patty, but Patty can also

be paired with Mike".

One would then discard half of the 380 pairs to obtain 190.

The second method is to construct the Combination of 20 items taken 2 at a time. Write this as

₂₀C₂ which translates to 20! divided by 2! divided by (20 − 2)!; this simplifies to (20 × 19) ÷ 2 or 190.