Counting permutations by their alternating runs (Q2474491)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting permutations by their alternating runs |
scientific article |
Statements
Counting permutations by their alternating runs (English)
0 references
6 March 2008
0 references
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\).
0 references
alternating runs
0 references
permutations
0 references
increasing and decreasing subsequences
0 references
asymptotic series
0 references
exact formula
0 references
0 references