Counting the nontrivial equivalence classes of S_n under \1234, 3412\-pattern-replacement

MaRDI QIDQ5129982zbMATH OpenFDO

Authors Quinn Perian, Bella Xu, Alexander Lu Zhang

Publication date 3 November 2020

Full work available at URL https://arxiv.org/abs/2008.02380, https://cs.uwaterloo.ca/journals/JIS/VOL23/Zhang/zhang6.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

equivalence classinteger sequencepattern-replacementpermutationpermutation patterntransposition

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: We study the $1234,3412$ pattern-replacement equivalence relation on the set $S_n$ of permutations of length $n$, which is conceptually similar to the Knuth relation. In particular, we enumerate and characterize the nontrivial equivalence classes, or equivalence classes with size greater than 1, in $S_n$ for $ngeq7$ under the $1234,3412$-equivalence. This proves a conjecture by Ma, who found three equivalence relations of interest in studying the number of nontrivial equivalence classes of $S_n$ under pattern-replacement equivalence relations with patterns of length $4$, enumerated the nontrivial classes under two of these relations, and left the aforementioned conjecture regarding enumeration under the third as an open problem.

Recommendations

• Counting permutations modulo pattern-replacement equivalences for three-letter patterns
• Equivalence classes of permutations modulo replacements between 123 and two-integer patterns
• New results on families of pattern-replacement equivalences
• Equivalence classes of permutations under various relations generated by constrained transpositions
• Equivalence relations of permutations generated by constrained transpositions

Cites work

• Adjacent transformations in permutations
• An equivalence relation on the symmetric group and multiplicity-free flag \(h\)-vectors
• Equivalence classes of permutations under various relations generated by constrained transpositions
• Excluded permutation matrices and the Stanley-Wilf conjecture
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• New results on families of pattern-replacement equivalences
• Pattern avoidance for alternating permutations and Young tableaux
• Restricted permutations
• The forgotten monoid

Cited in

(3)

• Counting consecutive pattern matches in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
• New results on families of pattern-replacement equivalences
• Counting permutations modulo pattern-replacement equivalences for three-letter patterns

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Counting the nontrivial equivalence classes of \(S_n\) under \(\{1234, 3412\}\)-pattern-replacement

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