Pattern Avoidance in Set Partitions

Abstract

The study of patterns in permutations in a very active area of current research. Klazar defined and studied an analogous notion of pattern for set partitions. We continue this work, finding exact formulas for the number of set partitions which avoid certain specific patterns. In particular, we enumerate and characterize those partitions avoiding any partition of a 3-element set. This allows us to conclude that the corresponding sequences are P-recursive. Finally, we define a second notion of pattern in a set partition, based on its restricted growth function. Related results are obtained for this new definition.

15 pages, see related papers at http://www.math.msu.edu/~sagan

References in corpus (3)

• Problems and Conjectures presented at the Third International Conference on Permutation Patterns, University of Florida, March 7-11, 2005
• Saturated chains in composition posets
• The Möbius function of the composition poset

Cited by in corpus (26)

• On Multiple Pattern Avoiding Set Partitions
• Schröder Paths and Pattern Avoiding Partitions
• Enumeration of $(k,2)$-noncrossing partitions
• Permutation classes and polyomino classes with excluded submatrices
• Pattern Avoidance in Poset Permutations
• Asymptotic results on Klazar set partition avoidance
• Pattern avoidance for set partitions à la Klazar
• Avoiding Colored Partitions of Lengths Two and Three
• Set partition statistics and q-Fibonacci numbers
• Avoidance of Partitions of a Three-element Set
• Avoiding colored partitions of two elements in the pattern sense
• Patterns in words of ordered set partitions
• On pattern-avoiding partitions
• The Dyck pattern poset
• Set partition patterns and statistics
• $K$ block set partition patterns and statistics
• On the dimension of downsets of integer partitions and compositions
• Pattern Avoidance in Task-Precedence Posets
• Pattern Avoidance in Ordered Set Partitions
• On Packing Densities of Set Partitions
• Enumeration schemes for vincular patterns
• Pattern Matching in Set Partitions is NP-Complete
• Set Partition Patterns and the Dimension Index
• Pattern avoidance and dominating compositions
• Combinatorial statistics on restricted growth functions containing a pattern exactly $k$ times
• Pattern Avoidance in Set Partitions