Wilf equivalence relations for consecutive patterns

Abstract

Two permutations $π$ and $τ$ are c-Wilf equivalent if, for each $n$, the number of permutations in $S_n$ avoiding $π$ as a consecutive pattern (i.e., in adjacent positions) is the same as the number of those avoiding $τ$. In addition, $π$ and $τ$ are strongly c-Wilf equivalent if, for each $n$ and $k$, the number of permutations in $S_n$ containing $k$ occurrences of $π$ as a consecutive pattern is the same as for $τ$. In this paper we introduce a third, more restrictive equivalence relation, defining $π$ and $τ$ to be super-strongly c-Wilf equivalent if the above condition holds for any set of prescribed positions for the $k$ occurrences. We show that, when restricted to non-overlapping permutations, these three equivalence relations coincide. We also give a necessary condition for two permutations to be strongly c-Wilf equivalent. Specifically, we show that if $π,τ$ in $S_m$ are strongly c-Wilf equivalent, then $|π_m-π_1|=|τ_m-τ_1|$. In the special case of non-overlapping permutations $π$ and $τ$, this proves a weaker version of a conjecture of the second author stating that $π$ and $τ$ are c-Wilf equivalent if and only if $π_1=τ_1$ and $π_m=τ_m$, up to trivial symmetries. Finally, we strengthen a recent result of Nakamura and Khoroshkin-Shapiro giving sufficient conditions for strong c-Wilf equivalence.