On Super-Strong Wilf Equivalence Classes of Permutations

Abstract

Super-strong Wilf equivalence is a type of Wilf equivalence on words that was originally introduced as strong Wilf equivalence by Kitaev et al. [Electron. J. Combin. 16(2)] in $2009$. We provide a necessary and sufficient condition for two permutations in $n$ letters to be super-strongly Wilf equivalent, using distances between letters within a permutation. Furthermore, we give a characterization of such equivalence classes via two-colored binary trees. This allows us to prove, in the case of super-strong Wilf equivalence, the conjecture stated in the same article by Kitaev et al. that the cardinality of each Wilf equivalence class is a power of $2$.