| Summary: | In 2000 Klazar introduced a new notion of pattern avoidance in the context of
set partitions of $[n]=\{1,\ldots, n\}$. The purpose of the present paper is to
undertake a study of the concept of Wilf-equivalence based on Klazar's notion.
We determine all Wilf-equivalences for partitions with exactly two blocks, one
of which is a singleton block, and we conjecture that, for $n\geq 4$, these are
all the Wilf-equivalences except for those arising from complementation. If
$\tau$ is a partition of $[k]$ and $\Pi_n(\tau)$ denotes the set of all
partitions of $[n]$ that avoid $\tau$, we establish inequalities between
$|\Pi_n(\tau_1)|$ and $|\Pi_n(\tau_2)|$ for several choices of $\tau_1$ and
$\tau_2$, and we prove that if $\tau_2$ is the partition of $[k]$ with only one
block, then $|\Pi_n(\tau_1)| <|\Pi_n(\tau_2)|$ for all $n>k$ and all partitions
$\tau_1$ of $[k]$ with exactly two blocks. We conjecture that this result holds
for all partitions $\tau_1$ of $[k]$. Finally, we enumerate $\Pi_n(\tau)$ for
all partitions $\tau$ of $[4]$.
|
|---|