we must put n students (where n is even) into n 2 partnerships. (We don’t care about the order of the partnerships, nor about the order of partners within a pair.) Here is an alternative way of...

we must put n students (where n is even) into n 2 partnerships. (We don’t care about the order of the partnerships, nor about the order of partners within a pair.) Here is an alternative way of solving this problem: Consider sorting the n people alphabetically by name. Repeat the following n 2 times: for the unmatched person p whose name is alphabetically first, choose a partner for p from the set of all other unmatched people. How many choices are there in iteration i? How many choices are there, in

total?