On 021-avoiding ascent sequences

William Y.C. Chen¹ ; Alvin Y.L. Dai¹ ; Theodore Dokos² ; Tim Dwyer³ ; Bruce E. Sagan⁴

¹Center for Combinatorics Nankai University
²Department of Mathematics University of California
³Department of Mathematics Dartmouth College
⁴Department of Mathematics State University

The electronic journal of combinatorics, Tome 20 (2013) no. 1

Résumé

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.

Détail

DOI : 10.37236/2472

Classification : 05A05, 05A19
Mots-clés : 021-avoiding ascent sequence, 132-avoiding permutation, right-to-left minimum, number of ascents, bijection