On 021-Avoiding Ascent Sequences

William Y.C. Chen, Alvin Y.L. Dai, Theodore Dokos, Tim Dwyer and Bruce E. Sagan

  Abstract:   Ascent sequences were introduced by Bousquet-Mélou, Claesson, Dukes and Kitaev in their study of (2 + 2)-free posets. An ascent sequence of length n is a nonnegative integer sequence x = x1 x2... xn such that x1 = 0 and xiasc(x1 x2... xi-1) + 1 for all 1 < i ≤ n, where asc(x1 x2... xi-1) is the number of ascents in the sequence x1 x2... xi-1. We let An stand for the set of such sequences and use An(p) for the subset of sequences avoiding a pattern p. Similarly, we let Sn(τ) be the set of τ-avoiding permutations in the symmetric group Sn. Duncan and Steingrímsson have shown that the ascent statistic has the same distribution over An(021) as over Sn(132). Furthermore, they conjectured that the pair (asc, rlm) is equidistributed over An(021) and Sn(132) where rlm is the right-to-left minima statistic. We prove this conjecture by constructing a bistatistic-preserving bijection.

  AMS Classification:  05A05, 05A19

  Keywords:   021-avoiding ascent sequence, 132-avoiding permutation, right-to-left minimum, number of ascents, bijection

  Download:   pdf