A new decomposition of ascent sequences and Euler--Stirling statistics

Abstract

As shown by Bousquet-Mélou--Claesson--Dukes--Kitaev (2010), ascent sequences can be used to encode $(2+2)$-free posets. It is known that ascent sequences are enumerated by the Fishburn numbers, which appear as the coefficients of the formal power series $$\sum _{m=1}^{\infty }\prod _{i=1}^m(1-(1-t{)}^i).$$ 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 $(\rep)$, 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ínek. This is accomplished via a bijective proof of the quadruple equidistribution of $(\asc,\rep,\zero,\max)$ and $(\rep,\asc,\rmin,\zero)$, where $\rmin$ 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 $(\rep,\max)$ on $(2-1)$-avoiding inversion sequences. This is achieved via a decomposition of $(2-1)$-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,\rep,\zero,\max)$ and $(\rep,\asc,\max,\zero)$ are equidistributed on ascent sequences.

25 pages, to appear in Journal of Combinatorial Theory, Series A