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]\).
Published: Discrete Math. Theor. Comput. Sci., vol 18(2), 2015, arXiv.