HMMT 二月 2008 · COMB 赛 · 第 7 题
HMMT February 2008 — COMB Round — Problem 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 is i the endpoint of at most one segment and (2) two no segments intersect. (The configuration with no edges drawn is allowed. An example of a valid configuration is shown below.) P 3 P P 4 2 P P 5 1 P P 6 8 P 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 is i the endpoint of at most one segment and (2) two no segments intersect. (The configuration with no edges drawn is allowed. An example of a valid configuration is shown below.) P 3 P P 4 2 P P 5 1 P P 6 8 P 7 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) ways to connect the remaining n − 1 points. If P belongs to an edge that separates the circle so that there are k points on one side and n − k − 2 points on the other side, then there are f ( k ) f ( n − k − 2) ways of finishing the configuration. Thus, f ( n ) satisfies the recurrence relation f ( 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 2 Richard Stanley’s Enumerative Combinatorics Volume 2, one can find 13 different interpretations of Motzkin numbers in exercise 6.38.