HMMT 十一月 2011 · THM 赛 · 第 5 题

英文解析

5. [ 8 ] For any finite sequence of positive integers π , let S ( π ) be the number of strictly increasing subsequences in π with length 2 or more. For example, in the sequence π = { 3 , 1 , 2 , 4 } , there are fiveincreasing sub-sequences: { 3 , 4 } , { 1 , 2 } , { 1 , 4 } , { 2 , 4 } , and { 1 , 2 , 4 } , so S ( π ) = 5. In an eight-playergame of Fish, Joy is dealt six cards of distinct values, which she puts in a random order π from left toright in her hand. Determine
   ∑
   S ( π ),
   where the sum is taken over all possible orders π of the card values.π
   Answer: 8287 For each subset of Joy’s set of cards, we compute the number of orders of cards inwhich the cards in the subset are arranged in increasing order. When we sum over all subsets of Joy’scards, we will obtain the desired sum.
   Consider any subset of k cards. The probability that they are arranged in increasing order is precisely
   1 /k ! (since we can form a k !-to-1 correspondence between all possible orders and orders in which thecards in our subset are in increasing order), and there are 6! = 720 total arrangements so exactly
   720 /k ! of them give an increasing subsequence in the specified cards. Now for any for k = 2 , 3 , 4 , 5 , 6,
   ( )
   we have subsets of k cards, so we sum to get 6
   ( )k
   ∑ ∑6
   6 6!
   S ( π ) = · = 8287.
   k k !
   k =2π