Enumeration of permutations by number of alternating runs

Shi-Mei Ma

Published 2011-10-23, updated 2012-11-28Version 7

Let R(n,k) denote the number of permutations of {1,2,...,n} with k alternating runs. We find a grammatical description of the numbers R(n,k) and then present several convolution formulas involving the generating function for the numbers R(n,k). Moreover, we establish a connection between alternating runs and Andre permutations.