Ballot permutations and odd order permutations

DOI10.1016/J.DISC.2020.111869MaRDI QIDQ2174607zbMATH OpenOpenAlexFDO

Authors Sam Spiro

Publication date 21 April 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

ballotpermutationsup-down signature

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19)

Abstract: A permutation $pi$ is ballot if, for all $k$, the word $p{i}_{1}cdotsp{i}_k$ has at least as many ascents as it has descents. Let $b(n)$ denote the number of ballot permutations of order $n$, and let $p(n)$ denote the number of permutations which have odd order in the symmetric group $S_n$. Callan conjectured that $b(n)=p(n)$ for all $n$, which was proved by Bernardi, Duplantier, and Nadeau. We propose a refinement of Callan's original conjecture. Let $b(n,d)$ denote the number of ballot permutations with $d$ descents. Let $p(n,d)$ denote the number of odd order permutations with $M(pi)=d$, where $M(pi)$ is a certain statistic related to the cyclic descents of $pi$. We conjecture that $b(n,d)=p(n,d)$ for all $n$ and $d$. We prove this stronger conjecture for the cases $d=1,2,3$, and $d=lfloor(n-1)/2floor$, and in each of these cases we establish formulas for $b(n,d)$ involving Eulerian numbers and Eulerian-Catalan numbers.

Recommendations

• A Toeplitz property of ballot permutations and odd order permutations
• The peak and descent statistics over ballot permutations
• A decomposition of ballot permutations, pattern avoidance and Gessel walks
• Refined Eulerian numbers and ballot permutations
• scientific article; zbMATH DE number 4168687

Cites work

• A bijection between well-labelled positive paths and matchings
• Eulerian-Catalan numbers
• scientific article; zbMATH DE number 3263280 (Why is no real title available?)
• Number of permutations with prescribed up-down structure as a function of two variables
• On arithmetic and asymptotic properties of up-down numbers
• Up-down coefficients for permutations

Cited in

(8)

• The peak and descent statistics over ballot permutations
• Refined Eulerian numbers and ballot permutations
• A decomposition of ballot permutations, pattern avoidance and Gessel walks
• Counting Labeled Threshold Graphs with Eulerian Numbers
• scientific article; zbMATH DE number 4168687 (Why is no real title available?)
• A complete enumeration of Ballot permutations avoiding sets of small patterns
• Callan permutations and odd order permutations
• A Toeplitz property of ballot permutations and odd order permutations

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Ballot permutations and odd order permutations

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