Alternating Permutations And Set Partitions With Restrictions

Permutations and set partitions with restrictions have received extensive atten-tion from many famous scholars including Stanley, Zeilberger, etc. For a thorough summary of the current status of research on pattern avoiding permutations, see Bona’s book and Kitaev’s book. Analogous to the ordinary permutations, Man-sour initiated the study of alternating permutations avoiding a given pattern. For any pattern of length3, the number of alternating permutations of a given length avoiding that pattern is given by Catalan numbers. Recently, Lewis considered the enumeration of alternating permutations avoiding a given pattern of length4.Set partitions with restrictions have received extensive attention from many scholars including Gessel, Klazar, Chen etc. Zagier derived the generating function for perfect matchings avoiding left and right nestings, which was firstly introduced by Stoimenow. Recently, Bousquet-Melou et al. constructed bijections between perfect matchings avoiding left nestings and right nestings and three other class-es of combinatorial objects, that is, unlabeled (2+2)-free posets, permutations avoiding a certain pattern and ascent sequences. Chen et al. derived the generat-ing functions for partial matchings avoiding neighbor alignments and for partial matchings avoiding neighbor alignments and left nestings. They obtained the generating function for partitions avoiding right nestings by presenting a bijection between partial matchings avoiding three neighbor patterns (left nestings, right nestings and neighbor alignments) and partitions avoiding right nestings. The thesis is mainly devoted to the problem of the enumeration of alternat-ing permutations and set partitions avoiding a given pattern. The main results obtained in this dissertation may be summarized as follows:In the first part, we establish bijections between the set of4123-avoiding down-up alternating permutations of length2n and the set of standard Young tableaux of shape (n, n, n), and between the set of4123-avoiding down-up alternating per-mutations of length2n-1and the set of shifted standard Young tableaux of shape (n+1, n, n-1) via an intermediate structure of Yamanouchi words. Moreover, we show that4123-avoiding up-down alternating permutations of length2n+1are in one-to-one correspondence with standard Young tableaux of shape (n+1, n, n-1), and4123-avoiding up-down alternating permutations of length2n are in bijection with shifted standard Young tableaux of shape (n+2, n, n-2).In the second part, we derive the generating function for partitions avoiding right crossings via an intermediate structure of partial matchings avoiding2-right crossings and right nestings. We show that there is a bijection between partial matchings avoiding2-right crossing and right nestings and partitions avoiding right crossings.