Pattern Avoidance In Ascent Sequences And Permutations

This thesis is mainly on permutations and ascent sequences. Pattern avoidance in permutations was first introduced by Knuth and then became an active research area during the past twenty years. Ascent sequences were introduced by Bousquet-M61ou, Claesson, Dukes and Kitaev in their study of (2+2)-free posets. Ascent sequences are closely connected to (2+2)-free posets, nonnegative upper-triangular matrices and Stoimenow’s matchings. In this thesis, we focus on the study of some statistics on021-avoiding ascent sequences,132-avoiding permutations and231-avoiding permutations.This thesis is organized as follows. In Chapter1, we shall briefly introduce the notions and histories of permutations and ascent sequences. We will also present some famous results in this research area.In Chapter2, we will build a bijection between021-avoiding ascent sequence and132-avoiding permutations. This bijection maps the pair of statistics (asc,rlmin) of a021-avoiding ascent sequence to the pair of statistics (asc, rlmin) of a132-avoiding per-mutation, which confirm the conjecture posed by Duncan and Steingrimsson that021-avoiding ascent sequences and132-avoiding permutations equidistributed on a pair of statistics (asc, rlmin). Moreover, our bijection can also be used to prove the statistic asc on021-avoiding ascent sequences and on132-avoiding permutations are equidistribut-ed.In Chapter3, we devote to enumerating the number of ascent sequences of length n avoiding the pattern R, where R is a subset of{000,001,012,010,011}. If the pattern R has the cardinality2, we proved that:the patterns{012,001},{012,010},{011,001},{010,001},{000,011},{010,011} and{011,012} are Wilf-equivalent. The patterns{000,001} and{000,010} are also Wilf-equivalent. We also obtain some results when the pattern R has the cardinality3and4. Finally, we prove that the cardi-nality of A0012(n) equals to the Catalan number Cn.In Chapter4, we concern with the recurrence relation F231(k)(x,t), G231(k)(x,t) and H231(k)(x,y,t)on231-avoiding permutations of length n with respect to the statistics (asc,maxdrop),(inv, maxdrop) and (inv, des,maxdrop), respectively. We also calcu-late the generation function for some special k and consider the coefficients of tn.