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.

05A05 Permutations, words, matrices
05A10 Factorials, binomial coefficients, combinatorial functions
05A15 Exact enumeration problems, generating functions
Full Text: EMIS