Journal of Integer Sequences, Vol. 23 (2020), Article 20.10.2

Counting the Nontrivial Equivalence Classes of Sn Under {1234,3412}-Pattern-Replacement

Quinn Perian
Stanford Online High School
Academy Hall Floor 2 8853
415 Broadway
Redwood City, CA 94063

Bella Xu
William P. Clements High School
4200 Elkins Drive
Sugar Land, TX 77479

Alexander Lu Zhang
Lower Merion High School
315 E. Montgomery Ave
Ardmore, PA 19003


We study the {1234, 3412}-pattern-replacement equivalence relation on the set Sn 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 Sn for n ≥ 7 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 Sn 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.

Full version:  pdf,    dvi,    ps,    latex,     C++ code    

(Concerned with sequences A330395.)

Received June 29 2020; revised versions received September 18 2020; October 16 2020. Published in Journal of Integer Sequences, October 17 2020.

Return to Journal of Integer Sequences home page