Ascent sequences and 3-nonnesting set partitions

Sherry H. F. Yan

paper

Ascent sequences and 3-nonnesting set partitions

arXiv:1208.1915

Abstract

A sequence x=x_1 x_2...x_n $i ss ai d t o b e ana sce n t se q u e n ceo f l e n g t h$ n $i f i t s a t i s f i es x_{1} = 0 an d$ 0\leq x_i\leq asc(x_1x_2...x_{i-1})+1 $f or a l l$ 2\leq i\leq n $, w h er e$ asc(x_1x_2... x_{i-1}) $i s t h e n u mb er o f a sce n t s in t h ese q u e n ce$ x_1x_2... x_{i-1} $. R ece n tl y, D u n c anan d S t e in g r ı ˊ m sso n p r o p ose d t h eco nj ec t u r e t ha t 210 - a v o i d in g a sce n t se q u e n ceso f l e n g t h$ n $a r ee q u in u m er o u s w i t h 3 - n o nn es t in g se tp a r t i t i o n so f$ \{1,2,..., n\} $. I n t hi s p a p er, w eco n f i r m t hi sco nj ec t u r e b y s h o w in g t ha t 210 - a v o i d in g a sce n t se q u e n ceso f l e n g t h$ n $a r e inbij ec t i o n w i t h 3 - n o nn es t in g se tp a r t i t i o n so f$ \{1,2,..., n\}$ via an intermediate structure of growth diagrams for 01-fillings of Ferrers shapes.

arXiv admin note: text overlap with arXiv:math/0510676 by other authors