On super-strong Wilf equivalence classes of permutations

Super-strong (elsewhere referred to as strong) Wilf equivalence is a type of Wilf equivalence on words that was introduced by Kitaev et al. in 2009. We provide a necessary and sufficient condition for two permutations in \(n\) letters to be super-strongly Wilf equivalent, using distances between let...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-06
Main Authors: Hadjiloucas, Demetris, Michos, Ioannis, Savvidou, Christina
Format: Article
Language:English
Subjects:
Equivalence
Permutations
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Super-strong (elsewhere referred to as strong) Wilf equivalence is a type of Wilf equivalence on words that was introduced by Kitaev et al. 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 (Kitaev et al., 2009) that the cardinality of each Wilf equivalence class is a power of 2.
ISSN:2331-8422