For a hereditary permutation class $\mathcal{ C}$, we say that two permutations $\pi$ and $\sigma$ of $\mathcal{ C}$ are Wilf-equivalent in $\mathcal{ C}$, if $\mathcal{ C}$ has the same number of permutations avoiding $\pi$ as those avoiding $\sigma$. We say that a permutation class $\mathcal{ C}$ exhibits a Wilf collapse if the number of permutations of size $n$ in $\mathcal{ C}$ is asymptotically larger than the number of Wilf-equivalence classes formed by these permutations. In this paper, we show that Wilf collapse is a surprisingly common phenomenon. Among other results, we show that Wilf collapse occurs in any permutation class with unbounded growth and finitely many sum-indecomposable permutations. Our proofs are based on encoding the elements of a permutation class $\mathcal{ C}$ as words, and analyzing the structure of a random permutation in $\mathcal{ C}$ using this representation.
Categories: math.CO