Discrete Mathematics & Theoretical Computer Science 
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 Wilfequivalence based on Klazar's notion. We determine all Wilfequivalences 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 Wilfequivalences 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]$.
Source : ScholeXplorer
IsRelatedTo ARXIV 1608.02279 Source : ScholeXplorer IsRelatedTo DOI 10.23638/dmtcs1927 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1608.02279
