DIMACS TR: 2006-19
Pattern Avoidance in Set Partitions
Author: Bruce E. Sagan
ABSTRACT
The study of patterns in permutations is 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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-19.ps.gz
DIMACS Home Page