PUMaC 2010 · 组合（B 组） · 第 8 题
PUMaC 2010 — Combinatorics (Division B) — Problem 8
题目详情
- Matt is asked to write the numbers from 1 to 10 in order, but he forgets how to count. He writes a permutation of the numbers { 1 , 2 , 3 . . . , 10 } across his paper such that: (a) The leftmost number is 1. (b) The rightmost number is 10. (c) Exactly one number (not including 1 or 10) is less than both the number to its immediate left and the number to its immediate right. How many such permutations are there? 1
解析
- Matt is asked to write the numbers from 1 to 10 in order, but he forgets how to count. He writes a permutation of the numbers { 1 , 2 , 3 . . . , 10 } across his paper such that: (a) The leftmost number is 1. (b) The rightmost number is 10. (c) Exactly one number (not including 1 or 10) is less than both the number to its immediate left and the number to its immediate right. How many such permutations are there? Answer: 1636 Solution: Consider the ”changes of direction” of the sequence of numbers. It must switch from decreasing to increasing exactly once by (3). By (1) and (2) it must start and end as increasing. Therefore the sequence must go from increasing to decreasing to increasing. Let a be the unique number that’s less than both its neighbors, corresponding to the switch from decreasing to increasing, and let b be the unique number that’s greater than both its neighbors, corresponding to the switch from increasing to decreasing. Then the sequence is of the form 1 , . . . , b, . . . , a, . . . , 10, where 1 < a < b < 10, and the sequence is monotonic between 1 and b , between b and a , and between a and 10. If we fix a and b , then the sequence is uniquely determined by the sets of numbers in each of the three dotted sections. In other words, we simply have to choose which of the three sections to place each of the remaining numbers. The numbers between 1 and a must go to the left of b , and the numbers between b and 10 must go to the right of a . The numbers between a and b can go in any of the three sections. For example, if a = 2, b = 8, and we divide the numbers between a and b into the sets { 4 , 6 } , { 3 } , { 5 , 7 } , then we obtain the unique permutation 1 , 4 , 6 , 8 , 3 , 2 , 5 , 7 , 9 , 10. Therefore the number of permutations is ∑ b − a − 1 N = 3 1 <a<b< 10 5 For each 1 ≤ n ≤ 7, if b − a = n , then 1 < a = b − n < 10 − n , so there are 8 − n possible values of a , each of which uniquely determines a value of b . Therefore, 7 6 ∑ ∑ n − 1 n N = (8 − n )3 = (7 − n )3 n =1 n =0 Multiplying the first expression above by 3, we obtain 7 ∑ n 3 N = (8 − n )3 n =1 Subtracting, we obtain 6 ∑ 7 0 n 2 N = (8 − 7)3 − (7 − 0)3 + 3 n =1 7 ∑ n = − 7 + 3 n =1 6 ∑ n = − 7 + 3 3 n =0 7 3 − 1 = − 7 + 3 · 3 − 1 = 3272 so N = 1636 . 6