On 021-avoiding ascent sequences (Q1953473)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On 021-avoiding ascent sequences
scientific article

    Statements

    On 021-avoiding ascent sequences (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    7 June 2013
    0 references
    Summary: Ascent sequences were introduced by Bousquet-Mélou, Claesson, Dukes and Kitaev in their study of \((\mathbf{2+2})\)-free posets. An ascent sequence of length \(n\) is a nonnegative integer sequence \(x=x_{1}x_{2}\ldots x_{n}\) such that \(x_{1}=0\) and \(x_{i}\leq \text{asc}(x_{1}x_{2}\ldots x_{i-1})+1\) for all \(1<i\leq n\), where \(\text{asc}(x_{1}x_{2}\ldots x_{i-1})\) is the number of ascents in the sequence \(x_{1}x_{2}\ldots x_{i-1}\). We let \(\mathcal{A}_n\) stand for the set of such sequences and use \(\mathcal{A}_n(p)\) for the subset of sequences avoiding a pattern \(p\). Similarly, we let \(S_{n}(\tau)\) be the set of \(\tau\)-avoiding permutations in the symmetric group \(S_{n}\). \textit{P. Duncan} and \textit{E. Steingrímsson} [ibid. 18, No. 1, Research Paper P226, 17 p., electronic only (2011; Zbl 1243.05010)] have shown that the ascent statistic has the same distribution over \(\mathcal{A}_n(021)\) as over \(S_n(132)\). Furthermore, they conjectured that the pair \((\text{asc}, \text{rmin})\) is equidistributed over \(\mathcal{A}_n(021)\) and \(S_n(132)\) where \(\text{rmin}\) is the right-to-left minima statistic. We prove this conjecture by constructing a bistatistic-preserving bijection.
    0 references
    021-avoiding ascent sequence
    0 references
    132-avoiding permutation
    0 references
    right-to-left minimum
    0 references
    number of ascents
    0 references
    bijection
    0 references

    Identifiers