MathDB
2011 PUMaC Combinatorics A5

Source:

September 24, 2019
combinatorics

Problem Statement

Let σ\sigma be a random permutation of {0,1,,6}\{0, 1, \ldots, 6\}. Let L(σ)L(\sigma) be the length of the longest initial monotonic consecutive subsequence of σ\sigma not containing 00; 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.L(\underline{2,3,4},6,5,1,0) = 3,\ L(\underline{3,2},4,5,6,1,0) = 2,\ L(0,1,2,3,4,5,6) = 0. If the expected value of L(σ)L(\sigma) can be written as mn\frac mn, where mm and nn are relatively prime positive integers, then find m+nm + n.