Counting permutations by alternating runs via Hetyei-Reiner trees

2025/12/13 by Qiongqiong Pan, Pan, Qiongqiong, Jiang Zeng +2
Mathematics · Biochemistry, Genetics and Molecular Biology · #Advanced Combinatorial Mathematics #Genome Rearrangement Algorithms #Advanced Mathematical Identities

paper · pdf · doi:10.48550/arxiv.2512.12275

Abstract

The generating polynomial of permutations of size n, counted by the number of alternating runs, has a root at -1 of multiplicity \lfloor (n-2)/2 \rfloor for all n ≥ 2. This result can be derived by combining the David--Barton formula for Eulerian polynomials with the Foata--Schützenberger γ--decomposition. More recently, Bóna gave a group--action proof of this phenomenon. In this paper, we present an alternative approach based on the Hetyei--Reiner action on binary trees, which leads to a new combinatorial interpretation of Bóna's quotient polynomial. Moreover, we extend our analysis to analogous results for permutations of types~B and~D. As a by--product of our bijective framework, we also obtain combinatorial proofs of David--Barton--type identities for permutations of types~A and~B.

Citations

• Enumeration of permutations by the parity of descent positions
• Springer Numbers and Arnold Families Revisited
• Generating functions of permutations with respect to their alternating runs
• Brändén's (p,q)-Eulerian polynomials, André permutations and continued fractions
• Gamma-positivity in combinatorics and geometry
• Andre Permutation Calculus; a Twin Seidel Matrix Sequence
• Counting permutations by alternating descents
• Enumeration of permutations by number of alternating runs
• Affine descents and the Steinberg torus
• Longest alternating subsequences of permutations
• A combinatorial proof of the log-concavity of the numbers of permutations with k runs
• q-Eulerian Polynomials Arising from Coxeter Groups

Related

• On the Alternating runs polynomial in type B and D Coxeter Groups
• Permutations with Extremal number of Fixed Points
• Non-overlapping descents and ascents in stack-sortable permutations
• Eulerian polynomials and excedance statistics
• Counting permutations by alternating descents