On 021-Avoiding Ascent Sequences

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

Abstract

Ascent sequences were introduced by Bousquet-Mélou, Claesson, Dukes and Kitaev in their study of $(\bf{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 {\rm asc}(x_{1}x_{2}\ldots x_{i-1})+1$ for all $1<i\leq n$, where ${\rm 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}$. Duncan and Steingrímsson 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 $({\rm asc}, {\rm rmin})$ is equidistributed over $\mathcal{A}_n(021)$ and  $S_n(132)$ where ${\rm rmin}$ is the right-to-left minima statistic.  We prove this conjecture by constructing a bistatistic-preserving bijection.

Published
2013-03-31
Article Number
P76