Let $pi in mathfrak{S}_m$ and $sigma in mathfrak{S}_n$ be permutations. An occurrence of $pi$ in $sigma$ as a consecutive pattern is a subsequence $sigma_i sigma_{i+1} cdots sigma_{i+m-1}$ of $sigma$ with the same order relations as $pi$. We say that patterns $pi, tau in mathfrak{S}_m$ are strongly c-Wilf equivalent if for all $n$ and $k$, the number of permutations in $mathfrak{S}_n$ with exactly $k$ occurrences of $pi$ as a consecutive pattern is the same as for $tau$. In 2018, Dwyer and Elizalde conjectured (generalizing a conjecture of Elizalde from 2012) that if $pi, tau in mathfrak{S}_m$ are strongly c-Wilf equivalent, then $(tau_1, tau_m)$ is equal to one of $(pi_1, pi_m)$, $(pi_m, pi_1)$, $(m+1 - pi_1, m+1-pi_m)$, or $(m+1 - pi_m, m+1 - pi_1)$. We prove this conjecture using the cluster method introduced by Goulden and Jackson in 1979, which Dwyer and Elizalde previously applied to prove that $|pi_1 - pi_m| = |tau_1 - tau_m|$. A consequence of our result is the full classification of c-Wilf equivalence for a special class of permutations, the non-overlapping permutations. Our approach uses analytic methods to approximate the number of linear extensions of the cluster posets of Elizalde and Noy.
تحميل البحث