# There are 39 students in our class. We form groups of 2, with one left out. How many ways can the students be paired up?

I know that the answer is $\frac{39!}{(2!)^{19}\cdot19!}$, where each pair can be organized $2!$ ways and the pairs can be arranged in $19!$ ways. We can also extrapolate the case for $5$ students, where I see that there are $15$ possible subsets ($\frac{5!}{2!^2\cdot2!}$).

What I don't understand is why we don't account for where the single student can be placed in our solution. There are $19!$ ways to organize the pairs, but aren't there $20!$ ways to arrange the pairs and the one extra student?

• Once you have picked all the pairs, the left out person is determined, there is no more arranging to do. Commented Jun 14, 2015 at 2:40
• Or else you can decide the lonesome student can be chosen in $39$ ways. For each of these ways we need to divide the remaining $38$ into pairs. You may know this can be done in $\frac{38!}{2^{19}(19!)}$ ways. Commented Jun 14, 2015 at 3:24

Consider this alternate process:

First, arrange the students in some arbitrary order: age, weight, IQ, whatever...

Now take a set of 39 cards. Two are labelled "Group #1", two are labelled "Group #2", and so on, up to "Group #19". The last, 39th card is labelled "On Your Own". (Note we're now accounting for the lone student). You are going to shuffle the cards, and then distribute them one by one, off the top, to the students in their arbitrary order.

How many distinct ways can you arrange 39 items, when there are 19 identical pairs and one item distinct from all the others?

Happening upon this question, I would like to show a simpler formula.

After selecting the solo person ($$39$$ choices), let us serially form pairs, i.e. the first person has $$37$$ choices for pairing, and each suceeding person will have two choices less, thus have $$37\cdot35\cdot33\cdot 31 \dots \cdot 3\cdot1$$ ways

This skipping by two product is called a double factorial, and the equivqlent formula can then be very neatly encapsulated as $$\boxed{39\cdot 37!!}$$, eliminating the complex looking divisors in the original formula, $$\boxed{\dfrac{39!}{(2!)^{19}\cdot19!}}$$

• I cringe when I see the notation $37!!!$ Commented Aug 16 at 15:53
• @JohnBentin: De gustibus non est disputandum ! Btw, you have made it cringer by making it read like a triple factorial ! Commented Aug 16 at 16:10