Ascent sequences and 3-nonnesting set partitions

A sequence x=x_1 x_2...x_n $is said to be an ascent sequence of length$n$if it satisfies x_1=0 and$0\leq x_i\leq asc(x_1x_2...x_{i-1})+1$for all$2\leq i\leq n$, where$asc(x_1x_2... x_{i-1})$is the number of ascents in the sequence$x_1x_2... x_{i-1}$. Recently, Duncan and Steingr\'ımsson proposed the conjecture that 210-avoiding ascent sequences of length$n$are equinumerous with 3-nonnesting set partitions of$\{1,2,..., n\}$. In this paper, we confirm this conjecture by showing that 210-avoiding ascent sequences of length$n$are in bijection with 3-nonnesting set partitions of$\{1,2,..., n\}$ via an intermediate structure of growth diagrams for 01-fillings of Ferrers shapes.

No reviews yet.

No comments yet.