Longest alternating subsequences of k-ary words
Recently, Stanley [Longest alternating subsequences of permutations, preprint, arXiv/0511419v1] studied the length of the longest alternating subsequence of a permutation in the symmetric group, where a sequence a,b,c,d, a , b , c , d ,  is alternating  if a>b d  b   d < ? . In this paper, we extend this result to the case of k-ary words. More precisely, we find an explicit formula for the generating function of the number of k-ary words of length n according to the length of the longest alternating subsequence.
05a05 05a15 05a16