Enumeration of permutations by number of alternating runs

Let S n denote the symmetric group of all permutations of { 1 , 2 , … , n } . In this paper, we consider the number R ( n , k ) of permutations in S n with k alternating runs, and the number a k ( n ) of permutations in S n with the longest alternating subsequence of length k . By using the grammatical method due to Chen, we obtain grammatical interpretations of the generating functions of these numbers, as well as convolution identities involving these generating functions. Moreover, we establish a connection between alternating runs and André permutations.