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₁ x₂... x_n such that x₁ = 0 and x_i ≤ asc(x₁ x₂... x_i-1) + 1 for all 1 < i ≤ n, where asc(x₁ x₂... x_i-1) is the number of ascents in the sequence x₁ x₂... 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