# zbMATH — the first resource for mathematics

Permutations with given peak set. (English) Zbl 1295.05008
Summary: 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 $${\mathcal 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 $$\# {\mathcal 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 $$\# {\mathcal P}(S;n)$$ when $$\# S$$ is fixed.

##### MSC:
 05A05 Permutations, words, matrices 05A10 Factorials, binomial coefficients, combinatorial functions 05A15 Exact enumeration problems, generating functions
##### Keywords:
binomial coefficient; peak; permutation
OEIS
Full Text: