Séminaire Lotharingien de Combinatoire, 78B.69 (2017), 12 pp.

Tim Dwyer and Sergi Elizalde

A necessary Condition for c-Wilf Equivalence

Abstract. Two permutations π and τ are strongly c-Wilf equivalent if, for each n and k, the number of permutations in Sn 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 Sm 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. 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.

Received: November 14, 2016. Accepted: February 17, 2017. Final version: April 1, 2017.

The following versions are available: