Permutations with given peak set
From MaRDI portal
Abstract: 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 > 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.
Recommendations
- The number of permutations with the same peak set for signed permutations
- Value-peaks of permutations
- A combinatorial proof for the enumeration of alternating permutations with given peak set
- Counting permutations by cyclic peaks and valleys
- The pinnacle set of a permutation
- Counting permutations by peaks, descents, and cycle type
- Sorting permutations with fixed pinnacle set
- scientific article; zbMATH DE number 1943960
- Permutations
Cited in
(37)- The number of permutations with the same peak set for signed permutations
- Special values of spectral zeta functions and combinatorics: Sturm-Liouville problems
- Parking Functions: Choose Your Own Adventure
- The peak statistics on simsun permutations
- A necessary condition for c-Wilf equivalence
- Counting peaks on graphs
- Pinnacle sets of signed permutations
- A combinatorial proof for the enumeration of alternating permutations with given peak set
- Wilf equivalence relations for consecutive patterns
- A formula for enumerating permutations with a fixed pinnacle set
- Pinnacle set properties
- scientific article; zbMATH DE number 763827 (Why is no real title available?)
- Factoring peak polynomials
- Coefficients and roots of peak polynomials
- Descent polynomials, peak polynomials and an involution on permutations
- On \(q\)-analogs of descent and peak polynomials
- A proof of the peak polynomial positivity conjecture
- Central limit theorem for peaks of a random permutation in a fixed conjugacy class of \(S_n\)
- Peak sets of classical Coxeter groups
- Metrics on permutations with the same peak set
- Counting signed permutations by their alternating runs
- Admissible pinnacle orderings
- Floodings of metric graphs
- Sorting permutations with fixed pinnacle set
- A proof of the peak polynomial positivity conjecture
- Value-peaks of permutations
- Descent polynomials for labeled trees
- On graphs of sets of reduced words
- Cyclic pattern containment and avoidance
- On meteors, earthworms and wimps
- On distribution of the number of peaks and the Euler numbers of permutations
- Roots of descent polynomials and an algebraic inequality on hook lengths
- Some coefficient sequences related to the descent polynomial
- Descent polynomials
- The pinnacle set of a permutation
- The peak algebra of the symmetric group
- Finitely dependent coloring
This page was built for publication: Permutations with given peak set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404323)
