PUMaC 2011 · 组合（A 组） · 第 5 题

PUMaC 2011 — Combinatorics (Division A) — Problem 5

[ 5 ] Let σ be a random permutation of { 0 , 1 , . . . , 6 } . Let L ( σ ) be the length of the longest initial monotonic consecutive subsequence of σ not containing 0; for example, L (2 , 3 , 4 , 6 , 5 , 1 , 0) = 3 , L (3 , 2 , 4 , 5 , 6 , 1 , 0) = 2 , L (0 , 1 , 2 , 3 , 4 , 5 , 6) = 0 . m If the expected value of L ( σ ) can be written as , where m and n are relatively prime positive n integers, then find m + n . n

解析

Suppose in general that σ is a permutation of a set of size n > 1. Let P [ L ( σ ) = l ] be the probability that L ( σ ) is equal to l , and define E [ L ( σ )] to be the expected value of L ( σ ). By definition of expected value, n n m n n ∑ ∑ ∑ ∑ ∑ E [ L ( σ )] = m · P [ L ( σ ) = m ] = P [ L ( σ ) = m ] = P [ L ( σ ) = m ] . m =0 m =1 l =1 l =1 m = l ∑ n Here, P [ L ( σ ) = m ] is exactly the probability P [ L ( σ ) ≥ l ] that L ( σ ) is at least l . We can m = l 2( n − l )!( n − l ) calculate that P [ L ( σ ) ≥ l ] = : after choosing between increasing and decreasing, n ! there are n − l possible starting values for our initial sequence of length l , and then we can choose any of the ( n − l )! arrangements of the last n − l elements of the permutation. Then, we have that 7 n ∑ ∑ n − 1 ( n − l )!( n − l ) E [ L ( σ )] = P [ L ( σ ) ≥ l ] = + 2 . n n ! l =1 l =2 Here, n n − 2 n − 2 ∑ ∑ ∑ ( n − l )!( n − l ) = l · l ! = ( l + 1)! − l ! = ( n − 1)! − 1 l =2 l =1 l =1 by telescoping. It follows that n − 1 2 · ( n − 1)! − 2 ( n + 1)( n − 1)! − 2 E [ L ( σ )] = + = . n n ! n ! 5758 2879 For n = 7, this yields = (note gcd(2879 , 2520) = gcd(359 , 2520) = gcd(359 , 7) = 1 by 5040 2520 the Euclidean algorithm, so this is reduced), so the answer is 5399 .