HMMT 二月 2009 · COMB 赛 · 第 10 题

英文解析

10. [ 8 ] Given a rearrangement of the numbers from 1 to n , each pair of consecutive elements a and b ofthe sequence can be either increasing (if a < b ) or decreasing (if b < a ). How many rearrangements ofthe 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 (whichnhas the two increasing pairs 15 and 26), the three sets are { 4 , 1 } , { 5 , 3 , 2 } , and 6. There are 3 ways tochoose which of the first, second, or third set each element is in. However, we have overcounted: somechoices 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 ofn nelements is 2 − ( n + 1). To do so, note that there are 2 ways to choose which elements occur beforethe 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 oneincreasing 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 onenincreasing pair is 2 − ( n + 1) as desired.
    We now count the partitions of { 1 , 2 , . . . , n } whose associated permutation has exactly one increasingnpair. 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 aren + 1 ways to choose the ”breaking point” to split one of the subsets into two. Thus there are a totalof ( n + 1)(2 − ( n + 1)) partitions whose associaated permutation has exactly one increasing pair.n
    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 splitn +22
    the numbers into three subsets, and so there are such partitions of { 1 , 2 , . . . , n } into three subsets.
    n n 32
    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.
    42