Pinnacle set properties

DOI10.1016/J.DISC.2022.112882MaRDI QIDQ2138977zbMATH OpenOpenAlexFDO

Authors Rachel Domagalski, Jinting Liang, Quinn Minnich, Bruce E. Sagan, Jamie Schmidt, Alexander Sietsema

Publication date 17 May 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.10388

zbMATH Keywords

ballot sequencebinomial coefficientpermutationpinnacle set

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Factorials, binomial coefficients, combinatorial functions (05A10) Exact enumeration problems, generating functions (05A15) Symmetric groups (20B30)

Abstract: Let pi = pi_1 pi_2 ... pi_n be a permutation in the symmetric group S_n written in one-line notation. The pinnacle set of pi, denoted Pin pi, is the set of all pi_i such that pi_{i-1} < pi_i > pi_{i+1}. This is an analogue of the well-studied peak set of pi where one considers values rather than positions. The pinnacle set was introduced by Davis, Nelson, Petersen, and Tenner who showed that it has many interesting properties. In particular, they proved that the number of subsets of [n] = {1, 2, ..., n} which can be the pinnacle set of some permutation is a binomial coefficient. Their proof involved a bijection with lattice paths and was somewhat involved. We give a simpler demonstration of this result which does not need lattice paths. Moreover, we show that our map and theirs are different descriptions of the same function. Davis et al. also studied the number of pinnacle sets with maximum m and cardinality d which they denoted by p(m,d). We show that these integers are ballot numbers and give two proofs of this fact: one using finite differences and one bijective. Diaz-Lopez, Harris, Huang, Insko, and Nilsen found a summation formula for calculating the number of permutations in S_n having a given pinnacle set. We derive a new expression for this number which is faster to calculate in many cases. We also show how this method can be adapted to find the number of orderings of a pinnacle set which can be realized by some pi in S_n.

Recommendations

• The pinnacle set of a permutation
• Pinnacle sets of signed permutations
• Further results on pinnacle sets
• A formula for enumerating permutations with a fixed pinnacle set
• Admissible pinnacle orderings

Cites work

• A formula for enumerating permutations with a fixed pinnacle set
• Admissible pinnacle orderings
• An A_-coalgebra structure on a closed compact surface
• Combinatorics: the art of counting
• Cyclic pattern containment and avoidance
• Cyclic shuffle compatibility
• Efficient recurrence for the enumeration of permutations with fixed pinnacle set
• Enumeration of alternating permutations according to peak sets
• Pattern avoidance in ``flattened partitions
• Pattern containment in circular permutations
• Patterns in colored circular permutations
• Permutations with given peak set
• Sorting permutations with fixed pinnacle set
• The pinnacle set of a permutation

Cited in

(11)

• The pinnacle set of a permutation
• A formula for enumerating permutations with a fixed pinnacle set
• Admissible pinnacle orderings
• Further results on pinnacle sets
• scientific article; zbMATH DE number 763827 (Why is no real title available?)
• Pinnacle sets of signed permutations
• Efficient recurrence for the enumeration of permutations with fixed pinnacle set
• Pinnacle sets revisited
• Log-concavity and log-convexity via distributive lattices
• Pinnacles for complex reflection groups
• Sorting permutations with fixed pinnacle set

This page was built for publication: Pinnacle set properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138977)