Michos, Ioannis and Savvidou, Christina - 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
Enumeration of super-strong Wilf equivalence classes of permutations in the generalized factor order

Authors: Michos, Ioannis and Savvidou, Christina

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
Submitted on: December 22, 2018
Keywords: Mathematics - Combinatorics,05A05, 05A15, 68R15


Share

Consultation statistics

This page has been seen 869 times.
This article's PDF has been downloaded 50 times.