HMMT 二月 2009 · COMB 赛 · 第 10 题
HMMT February 2009 — COMB Round — Problem 10
题目详情
- [ 8 ] Given a rearrangement of the numbers from 1 to n , each pair of consecutive elements a and b of the sequence can be either increasing (if a < b ) or decreasing (if b < a ). How many rearrangements of the numbers from 1 to n have exactly two increasing pairs of consecutive elements? Express your answer in terms of n .
解析
- [ 8 ] Given a rearrangement of the numbers from 1 to n , each pair of consecutive elements a and b of the sequence can be either increasing (if a < b ) or decreasing (if b < a ). How many rearrangements of the numbers from 1 to n have exactly two increasing pairs of consecutive elements? n n Answer: 3 − ( n + 1) · 2 + n ( n + 1) / 2 or equivalent Solution: Notice that each such permutation consists of 3 disjoint subsets of { 1 , . . . , n } whose union is { 1 , . . . , n } , each arranged in decreasing order. For instance, if n = 6, in the permutation 415326 (which n has the two increasing pairs 15 and 26), the three sets are { 4 , 1 } , { 5 , 3 , 2 } , and 6. There are 3 ways to choose which of the first, second, or third set each element is in. However, we have overcounted: some choices of these subsets result in permutations with 1 or 0 increasing pairs, such as { 6 , 5 , 4 } , { 3 , 2 } , { 1 } . Thus, we must subtract the number of ordered partitions of { 1 , 2 , . . . , n } into 3 subsets for which the minimum value of the first is not less than the maximum of the second, or the minimum value of the second is not less than the maximum of the third. We first prove that the number of permutations having exactly one increasing consecutive pair of n n elements is 2 − ( n + 1). To do so, note that there are 2 ways to choose which elements occur before the increasing pair, and upon choosing this set we must arrange them in decreasing order, followed by the remaining elements arranged in decreasing order. The resulting permutation will have either one increasing pair or none. There are exactly n + 1 subsets for which the resulting permutation has none, namely, {} , { n } , { n, n − 1 } , { n, n − 1 , n − 2 } , etc. Thus the total number of permutations having one n increasing pair is 2 − ( n + 1) as desired. We now count the partitions of { 1 , 2 , . . . , n } whose associated permutation has exactly one increasing n pair. For each of the 2 − ( n + 1) permutations p having exacly one increasing pair, there are n + 1 partitions of { 1 , 2 , . . . , n } into 3 subsets whose associated permutation is p . This is because there are n + 1 ways to choose the ”breaking point” to split one of the subsets into two. Thus there are a total n of ( n + 1)(2 − ( n + 1)) partitions whose associaated permutation has exactly one increasing pair. Finally, we must count the number of partitions whose associated permutation is n, n − 1 , . . . , 3 , 2 , 1, n +2 i.e. has no increasing pair. There are ways of placing two barriers between these elements to split 2 n +2 the numbers into three subsets, and so there are such partitions of { 1 , 2 , . . . , n } into three subsets. 2 3 n n Thus, subtracting off the partitions we did not want to count, the answer is 3 − ( n + 1)(2 − ( n + ( ) n +2 n n 1)) − = 3 − ( n + 1) · 2 + n ( n + 1) / 2. 2 4