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 = x_{1} x_{2}... x_{n} such that x_{1} = 0 and x_{i} ≤ asc(x_{1} x_{2}... x_{i-1}) + 1 for all 1 < i ≤ n, where asc(x_{1} x_{2}... x_{i-1}) is the number of ascents in the sequence x_{1} x_{2}... x_{i-1}. We let A_{n} stand for the set of such sequences and use A_{n}(p) for the subset of sequences avoiding a pattern p. Similarly, we let S_{n}(τ) be the set of τ-avoiding permutations in the symmetric group S_{n}. Duncan and Steingrímsson have shown that the ascent statistic has the same distribution over A_{n}(021) as over S_{n}(132). Furthermore, they conjectured that the pair (asc, rlm) is equidistributed over A_{n}(021) and S_{n}(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 |