Enumeration of super-strong Wilf equivalence classes of permutations in the generalized factor order

MaRDI QIDQ5207839zbMATH OpenFDO

Authors Christina Savvidou, I. C. Michos

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1803.08818, https://dmtcs.episciences.org/5880/pdf

zbMATH Keywords

generalized factor ordernon-interval permutationspatterns in permutationsshift equivalencesuper-strong Wilf equivalence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15)

Abstract: Super-strong Wilf equivalence classes of the symmetric group ${mathcalS}_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 ${mathcalS}_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).

Recommendations

• On super-strong Wilf equivalence classes of permutations
• Shift equivalence in the generalized factor order
• Wilf equivalence relations for consecutive patterns
• Constraining strong \(c\)-Wilf equivalence using cluster poset asymptotics
• Uniquely-Wilf classes

Cited in

(6)

• A new class of Wilf-equivalent permutations
• Wilf equivalence relations for consecutive patterns
• Shift equivalence in the generalized factor order
• On super-strong Wilf equivalence classes of permutations
• A necessary condition for c-Wilf equivalence
• On a refinement of Wilf-equivalence for permutations

This page was built for publication: Enumeration of super-strong Wilf equivalence classes of permutations in the generalized factor order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207839)