ABSTRACT
In this chapter, we focus on two goals: multiple pattern avoidance and restrictions that cannot be clearly characterized by patterns. Let us start our discussion with the first goal. While the case of set partitions avoiding a single pattern has attracted much attention (see Chapter 6), the case of multiple pattern avoidance remains less investigated. In particular, it is natural, as the next step, to consider set partitions avoiding either pairs or triples (or even set) of patterns. The study of multiple pattern avoidance on set partitions was initiated by Goyt [120] when he extended the results of Sagan [306] to cover the cardinalities of the set partitions in Pn that avoid a subset of P3; see Table 3.2. Following Goyt, several research papers on multiple pattern avoidance were published with the focus on the connections between set partitions that avoid a set of patterns and combinatorial structures. For instance, Mansour and Shattuck [236, 232, 233, 235, 239] presented connections between set partitions that avoid three patterns, left Mozkin numbers (see Section 7.5), Sequence A054391 (see Section 7.6), Generalized Catalan numbers (see Section 7.7), Catalan numbers (see Section 7.7) and Pell numbers (see Section 7.8). Actually, each of these connections focused on avoiding very special sets of patterns. This changed when Jel´ınek, Mansour, and Shattuck [149] classified the equivalence classes among pair of patterns of several general types as we will discus see in the next sections. First, they classified pairs of patterns (σ, τ) where σ ∈ P3 is a pattern with at least two distinct letters and τ ∈ Pk(σ). They provided an upper bound for the number of equivalence classes, and provided an explicit formula for the generating function of all such avoidance classes, showing that in all cases this generating function is rational; see Section 7.1. Next, they focused on the set of noncrossing set partitions that avoid a pattern, that is, avoiding a pair of patterns of the form (1212, τ), where τ ∈ Pk(1212). Here also, they provided several general equivalence criteria for pattern pairs of this type, and showed that these criteria account for all the equivalences observed when τ has a size of at most six; see Sections 7.2 and 7.3. The most popular subset of set partitions is the subset of noncrossing set partitions (see the introduction of the book), which has received a lot of attention from different branches of mathematics such as enumerative combinatorics and algebraic combinatorics (see also Chapters 9 and 10 for applications in computer science and physics). Maybe the main reason for the wide applications of noncrossing set partitions is this subset enumerated by
[149] performed a full classification of the equivalence classes of all the pairs (σ, τ), where σ, τ ∈ P4; see Section 7.4.
