Article ID Journal Published Year Pages File Type
420845 Discrete Applied Mathematics 2008 6 Pages PDF
Abstract

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>bd<⋯a>bd<⋯. 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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,