Enumeration of permutations by number of alternating runs

Let Sn denote the symmetric group of all permutations of {1,2,…,n}. In this paper, we consider the number R(n,k) of permutations in Sn with k alternating runs, and the number ak(n) of permutations in Sn 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.