On Super-Strong Wilf Equivalence Classes of Permutations

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 equiva...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2018-06, Vol.25 (2)
Main Authors: Hadjiloucas, Demetris, Michos, Ioannis, Savvidou, Christina
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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$.
ISSN:1077-8926
1077-8926
DOI:10.37236/6808