Solution: Take 2n people, and count how many ways there are to form n partnerships. We can do this by lining up the people in a row and then saying the first two are a pair, the next two are a pair, etc. This overcounts by a factor of 2^n x n! since the order of pairs doesn't matter, nor does the order within each pair. Alternatively, count the number of possibilities by noting that there are 2n - 1 choices for the partner of person 1, then 2n - 3 choices for person 2 (or person 3, if person 2 was already paired to person 1), etc.

Copyright © 2011 Stat 110 Harvard.
Website layout by former Stat110'er.