HMMT 二月 2008 · TEAM1 赛 · 第 3 题

英文解析

3. [ 20 ] Let n > 4 be a positive integer. Determine the number of ways to walk from (0 , 0) to
   ( n, 2) using only up and right unit steps such that the path does not meet the lines y = x ory = x − n + 2 except at the start and at the end.
   Answer: ( n − 5 n + 2)211
   Solution: It is easy to see the the first two steps and the last two steps must all be right 2
   steps. So we need to compute the number of walks from (2 , 0) to ( n − 2 , 0) that does not pass
   ( )
   n − 2
   through (2 , 2) and ( n − 2 , 0). There are paths from (2 , 0) to ( n − 2 , 0), and exactly two
   ( )2
   n − 2
   1 1 2
   of them are invalid. So the answer is − 2 = ( n − 2)( n − 3) − 2 = ( n − 5 n + 2).
   2 2 2