Wilf equivalence relations for consecutive patterns

Original · EN

Two permutations π and τ are c-Wilf equivalent if, for each n, the number of permutations in Sₙ 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ₙ 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ₘ are strongly c-Wilf equivalent, then |πₘ-π₁|=|τₘ-τ₁|. 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 π₁=τ₁ and πₘ=τₘ, up to trivial symmetries. Finally, we strengthen a recent result of Nakamura and Khoroshkin-Shapiro giving sufficient conditions for strong c-Wilf equivalence.