Longest alternating subsequences of permutations

Research paper by Richard P. Stanley

Indexed on: 16 Nov '05Published on: 16 Nov '05Published in: Mathematics - Combinatorics


The length is(w) of the longest increasing subsequence of a permutation w in the symmetric group S_n has been the object of much investigation. We develop comparable results for the length as(w) of the longest alternating subsequence of w, where a sequence a,b,c,d,... is alternating if a>b<c>d<.... For instance, the expected value (mean) of as(w) for w in S_n is exactly (4n+1)/6 if n>1.