Permutations with Given Peak Set

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 a_i-1<a_i>a_i+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.

Permutations with Given Peak Set

Sara Billey and Krzysztof Burdzy Department of Mathematics University of Washington Seattle, WA 98195-4350 USA Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027 USA

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

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