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 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]$.

Source: arXiv.org:1511.00192

Volume: Vol. 18 no. 2, Permutation Patterns 2015

Section: Permutation Patterns

Published on: September 7, 2016

Accepted on: September 7, 2016

Submitted on: September 7, 2016

Keywords: Mathematics - Combinatorics,05A18

This page has been seen 578 times.

This article's PDF has been downloaded 334 times.