Journal of Integer Sequences, Vol. 16 (2013), Article 13.6.1

Permutations with Given Peak Set

Sara Billey and Krzysztof Burdzy
Department of Mathematics
University of Washington
Seattle, WA 98195-4350

Bruce E. Sagan
Department of Mathematics
Michigan State University
East Lansing, MI 48824-1027 USA


Let ${\mathfrak S}_n$ denote the symmetric group of all permutations $\pi=a_1\cdots a_n$ of $\{1,\ldots,n\}$. An index i is a peak of $\pi$ if ai-1<ai>ai+1 and we let $P(\pi)$ be the set of peaks of $\pi$. Given any set S of positive integers we define ${\cal P}(S;n)=\{\pi\in{\mathfrak S}_n\ :\ P(\pi)=S\}$. Our main result is that for all fixed subsets of positive integers S and all sufficiently large n we have $\char93 {\cal P}(S;n)=p(n)2^{n-\char93 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 $\char93  {\cal P}(S;n)$ when $\char93 S$ is fixed.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000431 A008303.)

Received December 3 2012; revised version received May 22 2013. Published in Journal of Integer Sequences, June 5 2013.

Return to Journal of Integer Sequences home page