Ascent sequences and 3-nonnesting set partitions

Abstract: A sequence x=x_1 x_2...x_n

i s s a i d t o b e a n a s c e n t s e q u e n c e o f l e n g t h

n

i f i t s a t i s f i e s x_{1} = 0 a n d

0leq x_ileq asc(x_1x_2...x_{i-1})+1

f o r a l l

2leq ileq n

, w h e r e

asc(x_1x_2... x_{i-1})

i s t h e n u m b e r o f a s c e n t s i n t h e s e q u e n c e

x_1x_2... x_{i-1}

. R e c e n t l y, D u n c a n a n d S t e i n g r^{'} i m s s o n p r o p o s e d t h e c o n j e c t u r e t h a t 210 - a v o i d i n g a s c e n t s e q u e n c e s o f l e n g t h

n

a r e e q u i n u m e r o u s w i t h 3 - n o n n e s t i n g s e t p a r t i t i o n s o f

{1,2,..., n}

. I n t h i s p a p e r, w e c o n f i r m t h i s c o n j e c t u r e b y s h o w i n g t h a t 210 - a v o i d i n g a s c e n t s e q u e n c e s o f l e n g t h

n

a r e i n b i j e c t i o n w i t h 3 - n o n n e s t i n g s e t p a r t i t i o n s o f

{1,2,..., n}$ via an intermediate structure of growth diagrams for 01-fillings of Ferrers shapes.

Recommendations

Cites work

Cited in

(18)

Describes a project that uses

Uses Software

This page was built for publication: Ascent sequences and 3-nonnesting set partitions