Ballot permutations and odd order permutations

DOI10.1016/J.DISC.2020.111869zbMATH Open1437.05015arXiv1810.00993OpenAlexW3008734763MaRDI QIDQ2174607FDOQ2174607

Sam Spiro

Publication date: 21 April 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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 Keywords

permutationsballotup-down signature

Mathematics Subject Classification ID

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

Cites Work

• A bijection between well-labelled positive paths and matchings
• Number of permutations with prescribed up-down structure as a function of two variables
• Title not available (Why is that?)
• Up-down coefficients for permutations
• On arithmetic and asymptotic properties of up-down numbers
• Eulerian-Catalan numbers

Cited In (6)

• Counting Labeled Threshold Graphs with Eulerian Numbers
• Title not available (Why is that?)
• A decomposition of ballot permutations, pattern avoidance and Gessel walks
• The peak and descent statistics over ballot permutations
• Refined Eulerian numbers and ballot permutations
• A complete enumeration of Ballot permutations avoiding sets of small patterns

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)