HMMT 二月 2006 · COMB 赛 · 第 9 题

英文解析

9. Eight celebrities meet at a party. It so happens that each celebrity shakes hands withexactly two others. A fan makes a list of all unordered pairs of celebrities who shookhands with each other. If order does not matter, how many different lists are possible?
   Answer: 3507
   Solution: Let the celebrities get into one or more circles so that each circle hasat least three celebrities, and each celebrity shook hands precisely with his or herneighbors in the circle.
   Let’s consider the possible circle sizes:
   • There’s one big circle with all 8 celebrities. Depending on the ordering of thepeople in the circle, the fan’s list can still vary. Literally speaking, there are 7!
   different circles 8 people can make: fix one of the people, and then there are 7
   choices for the person to the right, 6 for the person after that, and so on. Butthis would be double-counting because, as far as the fan’s list goes, it makes nodifference if we “reverse” the order of all the people. Thus, there are 7! / 2 = 2520
   different possible lists here.
   ( )
   4!8
   • 5+3. In this case there are ways to split into the two circles, essentially
   5 2
   2!
   different ways of ordering the 5-circle, and ways for the 3-circle, giving a totalcount of 56 · 12 · 1 = 672.2
   ( )
   • 4+4. In this case there are / 2 = 35 ways to split into the two circles (we divide 8
   by 2 because here, unlike in the 5 + 3 case, it does not matter which circle is 4
   3!
   which), and = 3 ways of ordering each, giving a total count of 35 · 3 · 3 = 315.
   Adding them up, we get 2520 + 672 + 315 = 3507 .2