The Rearrangement Conjecture states that if two words over $\mathbb{P}$ are Wilf-equivalent in the factor order on $\mathbb{P}^{\ast}$ then they are rearrangements of each other. We introduce the notion of strong Wilf-equivalence and prove that if two words over $\mathbb{P}$ are strongly Wilf-equivalent then they are rearrangements of each other. We further conjecture that Wilf-equivalence implies strong Wilf-equivalence.
Discrete Mathematics & Theoretical Computer Science
