Permutations with given peak set

By Sara C. Billey, Krzysztof Burdzy, Bruce E. Sagan. 2012

57 citations recorded by the source corpus.

Let Sym_n denote the symmetric group of all permutations pi = a_1...a_n of {1,...,n}. An index i is a peak of pi if a_{i-1} a_{i+1} and we let P(pi) be the set of peaks of pi. Given any set S of positive integers we define P(S;n) to be the set pi in Sym_n with P(pi)=S. Our main result is that for all fixed subsets of positive integers S and all sufficiently large n we have #P(S;n)= p(n) 2^{n-#S-1} for some polynomial p(n) depending on S. We explicitly compute p(n) for various S of probabilistic interest, including certain cases where S depends on n. We also discuss two conjectures, one about positivity of the coefficients of the expansion of p(n) in a binomial coefficient basis, and the other about sets S maximizing #P(S;n) when #S is fixed.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/c621289d881c71d08a2b6487c3ddc0e782719e19