Counting permutations by their alternating runs (Q2474491)

An alternating run of a permutation \(\pi\) is an increasing or decreasing sequence of consecutive letters of \(\pi\) with maximal length. The number \(P(n,s)\) of permutations of \([n]\) having exactly \(s\) alternating runs has been the object of numerous studies. In this paper, the authors give an exact formula for \(P(n,s)\) which is simultaneously asymptotical for \(n\to\infty\) and \(s\leq(1-\varepsilon)n/\log n\) where \(\varepsilon>0\). Their approach is based on the generating functions \(\sum_{n\geq 2} P(n,s)x^n\).