A new decomposition of ascent sequences and Euler-Stirling statistics

DOI10.1016/J.JCTA.2019.105141zbMATH Open1428.05035arXiv1909.07277OpenAlexW2976126042MaRDI QIDQ2010641FDOQ2010641

Emma Yu Jin, Sherry H. F. Yan, Robin D. P. Zhou, Zhicong Lin, Shishuo Fu

Publication date: 27 November 2019

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: As shown by Bousquet-M'elou--Claesson--Dukes--Kitaev (2010), ascent sequences can be used to encode $$-free posets. It is known that ascent sequences are enumerated by the Fishburn numbers, which appear as the coefficients of the formal power series ${\displaystyle }$sum_{m=1}^{infty}prod_{i=1}^m (1-(1-t)^i).${\displaystyle }$ In this paper, we present a novel way to recursively decompose ascent sequences, which leads to: (i) a calculation of the Euler--Stirling distribution on ascent sequences, including the numbers of ascents ($asc$), repeated entries $(ep)$, zeros ($zero$) and maximal entries ($max$). In particular, this confirms and extends Dukes and Parviainen's conjecture on the equidistribution of $zero$ and $max$. (ii) a far-reaching generalization of the generating function formula for $(asc,zero)$ due to Jel'inek. This is accomplished via a bijective proof of the quadruple equidistribution of $(asc,ep,zero,max)$ and $(ep,asc,min,zero)$, where $min$ denotes the right-to-left minima statistic of ascent sequences. (iii) an extension of a conjecture posed by Levande, which asserts that the pair $(asc,zero)$ on ascent sequences has the same distribution as the pair $(ep,max)$ on $$-avoiding inversion sequences. This is achieved via a decomposition of $$-avoiding inversion sequences parallel to that of ascent sequences. This work is motivated by a double Eulerian equidistribution of Foata (1977) and a tempting bi-symmetry conjecture, which asserts that the quadruples $(asc,ep,zero,max)$ and $(ep,asc,max,zero)$ are equidistributed on ascent sequences.

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

zbMATH Keywords

ascentsascent sequencesFishburn numbers\((2 - 1)\)-avoiding inversion sequencesdistinct entriesmaximal entries

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19) Combinatorics of partially ordered sets (06A07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Intransitive indifference with unequal indifference intervals
• Vassiliev invariants and a strange identity related to the Dedekind eta-function
• Fishburn diagrams, Fishburn numbers and their refined generating functions
• ENUMERATION OF CHORD DIAGRAMS AND AN UPPER BOUND FOR VASSILIEV INVARIANTS
• Counting general and self-dual interval orders
• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• Enumerating \((2 + 2)\)-free posets by indistinguishable elements
• Ascent sequences and upper triangular matrices containing non-negative integers
• Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
• Interpretations combinatoires des nombres de Genocchi
• $n!$ matchings, $n!$ posets
• On a conjecture about enumerating \((2+2)\)-free posets
• Catalan pairs and Fishburn triples
• A sextuple equidistribution arising in pattern avoidance
• A permutation code preserving a double Eulerian bistatistic
• Equidistributed statistics on Fishburn matrices and permutations
• Refined restricted inversion sequences
• A note on \(p\)-ascent sequences

Cited In (13)

• Combinatorics of the symmetries of ascents in restricted inversion sequences
• On \(\underline{12} 0\)-avoiding inversion and ascent sequences
• Patterns of relation triples in inversion and ascent sequences
• Enumerating pattern-avoiding Fishburn permutations subject to seven statistics
• Fishburn trees
• Difference ascent sequences
• Inversion sequences avoiding pairs of patterns
• Wilf equivalences between vincular patterns in inversion sequences
• Asymptotics and statistics on Fishburn matrices: Dimension distribution and a conjecture of Stoimenow
• Symmetric generating functions and Euler-Stirling statistics on permutations
• Bi-symmetric multiple equidistributions on ascent sequences
• On enumeration of pattern-avoiding Fishburn permutations
• Asymptotics and statistics on Fishburn matrices and their generalizations

Uses Software

• OEIS

   Recommendations

• The ascent-plateau statistics on Stirling permutations 👍 👎
• Asymptotic Estimates of Stirling Numbers 👍 👎
• Title not available (Why is that?) 👍 👎
• Eulerian polynomials and descent statistics 👍 👎
• New Euler-Mahonian permutation statistics 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Probabilistic methods for obtaining asymptotic formulas for generalized Stirling numbers 👍 👎
• Title not available (Why is that?) 👍 👎
• Some enumerative results related to ascent sequences 👍 👎

This page was built for publication: A new decomposition of ascent sequences and Euler-Stirling statistics

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