Tuesday, August 10, 2010
Last week I heard a talk by Richard Stanley in which he mentioned a version of the following problem. Define an alternating sequence as one in which the differences between adjacent elements are alternatively positive and negative. So 1,2,3 and 3,2,1 are not alternating sequences but 1,4,2,5,3,6 is. Consider random permutations of 1,2,...,n. We ask as n goes to infinity what is the expected length of the longest alternating subsequence? Note the elements of a subsequence do not have to be adjacent in the original sequence. You can think of a subsequence as what is left after you delete some elements of a sequence.