Pattern Avoidance In Partitions And Matchings

In recent years, the subject of pattern avoidance in set partitions and matchings has been wildly studied. More and more classical combinatorial results have been extended for the partition case. The main results of this thesis consist of several approaches to study the enumeration of partitions and matchings avoiding certain patterns, including the bijective method, the transfer matrix method, and a method of developing a Maple package to produce D-finite equations based on the theory of constant terms.This thesis is organized as follows. The first Chapter is devoted to an introduction to set partitions and its related combinatorial objects. We will present some basic definitions and the classical notations.The RSK algorithm, named after G. de B. Robinson, C. Schensted, and D. Knuth, is perhaps the most beautiful and important algorithm in combinatorics. In its most basic form, it transforms a permutation into a pair of standard Young tableaux of the same shape. Schützenberger's theorem for ordinary RSK correspondence naturally extends for Chen et. al's correspondence for matchings and partitions. Based on the same symmetric property, we count the bilaterally symmetric k-noncrossing partitions which naturally arises as an analogue for involutions in Chapter 2. In obtaining the analogous result for 3-noncrossing partitions, we use a different technique to develop a Maple package for 2-dimensional vacillating lattice walk enumeration problems. The package also applies to the hesitating case. As applications, we find several interesting relations for some special bilaterally symmetric partitions.In Chapter 3, we turn to count the k-stack sortable partitions and matchings. A partition or a matching is said to be k-stack sortable if its canonical sequence is k-stack sortable. We show that a partition is k-stack sortable if and only if its canonical sequence is 23…(k + 2)1-avoiding. The explicit formulas for the generating functions for the numbers of k-stack sortable noncrossing partitions, noncrossing matchings and nonnesting matchings are obtained. Using the transfer matrix method we show that the generating function for the number of k-stack sortable matchings is rational. Moreover, we construct a simple bijection between the set of partitions of [n] with no more than k + 2 blocks and the set of k-stack sortable partitions of [n], which induces simpler formulas for the number of k-stack sortable partitions and for the generating function compared with the formulas of Mansour and Severini.We conclude this thesis with the Maple package developed in Chapter 2 and the initial variables when the package applies to the hesitating case.