Ioannis Michos ; Christina Savvidou - Enumeration of super-strong Wilf equivalence classes of permutations in the generalized factor order

dmtcs:5055 - Discrete Mathematics & Theoretical Computer Science, November 11, 2019, Vol. 21 no. 2, Permutation Patters 2018 - https://doi.org/10.23638/DMTCS-21-2-3
Enumeration of super-strong Wilf equivalence classes of permutations in the generalized factor orderArticle

Authors: Ioannis Michos ; Christina Savvidou

    Super-strong Wilf equivalence classes of the symmetric group ${\mathcal S}_n$ on $n$ letters, with respect to the generalized factor order, were shown by Hadjiloucas, Michos and Savvidou (2018) to be in bijection with pyramidal sequences of consecutive differences. In this article we enumerate the latter by giving recursive formulae in terms of a two-dimensional analogue of non-interval permutations. As a by-product, we obtain a recursively defined set of representatives of super-strong Wilf equivalence classes in ${\mathcal S}_n$. We also provide a connection between super-strong Wilf equivalence and the geometric notion of shift equivalence---originally defined by Fidler, Glasscock, Miceli, Pantone, and Xu (2018) for words---by showing that an alternate way to characterize super-strong Wilf equivalence for permutations is by keeping only rigid shifts in the definition of shift equivalence. This allows us to fully describe shift equivalence classes for permutations of size $n$ and enumerate them, answering the corresponding problem posed by Fidler, Glasscock, Miceli, Pantone, and Xu (2018).


    Volume: Vol. 21 no. 2, Permutation Patters 2018
    Section: Permutation Patterns
    Published on: November 11, 2019
    Accepted on: October 15, 2019
    Submitted on: December 22, 2018
    Keywords: Mathematics - Combinatorics,05A05, 05A15, 68R15

    Consultation statistics

    This page has been seen 1253 times.
    This article's PDF has been downloaded 241 times.