A necessary Condition for c-Wilf Equivalence

Tim Dwyer   ; Sergi Elizalde

Séminaire lotharingien de combinatoire, 78B (2017)

Résumé

Two permutations π 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 (i.e., in adjacent positions) is the same as for τ. If the condition holds for any set of prescribed positions for the k occurrences, we say that π and τ are super-strongly c-Wilf equivalent, and if it holds for k=0, we say that π and τ are c-Wilf equivalent.

We 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-π₁| = |τ_m-τ₁|. 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 π_m = τ_m, up to trivial symmetries. Additionally, we show that for non-overlapping permutations, c-Wilf equivalence coincides with super-strong c-Wilf equivalence, and we strengthen a recent result of Nakamura and Khoroshkin-Shapiro giving sufficient conditions for strong c-Wilf equivalence.