HMMT 二月 2008 · COMB 赛 · 第 7 题

英文解析

7. [ 6 ] Let P , P , . . . , P be 8 distinct points on a circle. Determine the number of possible configurations
   1 2 8
   made by drawing a set of line segments connecting pairs of these 8 points, such that: (1) each P isithe endpoint of at most one segment and (2) two no segments intersect. (The configuration with noedges drawn is allowed. An example of a valid configuration is shown below.)
   3P
   P P
   4 2
   P P
   5 1
   P P
   6 8
   7P
   Answer: 323 Let f ( n ) denote the number of valid configurations when there are n points on the circle. Let P be one of the points. If P is not the end point of an edge, then there are f ( n − 1) waysto connect the remaining n − 1 points. If P belongs to an edge that separates the circle so that thereare k points on one side and n − k − 2 points on the other side, then there are f ( k ) f ( n − k − 2) waysof finishing the configuration. Thus, f ( n ) satisfies the recurrence relationf ( n ) = f ( n − 1) + f (0) f ( n − 2) + f (1) f ( n − 3) + f (2) f ( n − 4) + · · · + f ( n − 2) f (0) , n ≥ 2 .
   The initial conditions are f (0) = f (1) = 1. Using the recursion, we find that f (2) = 2 , f (3) = 4 , f (4) =
   9 , f (5) = 21 , f (6) = 51 , f (7) = 127 , f (8) = 323.
   Remark: These numbers are known as the Motzkin numbers. This is sequence A001006 in the On-Line
   Encyclopedia of Integer Sequences ( http://www.research.att.com/~njas/sequences/A001006 ). In
   Richard Stanley’s Enumerative Combinatorics Volume 2, one can find 13 different interpretations of 2
   Motzkin numbers in exercise 6.38.