The Rearrangement Conjecture

Abstract

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.

Keywords

• composition
• generalized factor order
• wilf-equivalence
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]