On super-strong Wilf equivalence classes of permutations (Q1648664)

Summary: Super-strong Wilf equivalence is a type of Wilf equivalence on words that was originally introduced as strong Wilf equivalence by \textit{S. Kitaev} et al. in [Electron. J. Comb. 16, No. 2, Research Paper R22, 26 p. (2009; Zbl 1187.05010)]. 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. [loc. cit.] that the cardinality of each Wilf equivalence class is a power of \(2\).