Equivalence classes of permutations under various relations generated by constrained transpositions

Stephen Alexander Linton, James Propp, Tom Roby, Julian West

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


We consider a large family of equivalence relations on the symmetric group of permutations of n that generalize those discovered by Knuth in his study of the Robinson-Schensted correspondence. In our most general setting, two permutations are equivalent if one can be obtained from the other by a sequence of pattern-replacing moves of prescribed form; however, we limit our focus to patterns where two elements are transposed, subject to the constraint that a third element of a suitable type be in a suitable position. For various instances of the problem, we compute the number of equivalence classes, determine how many n-permutations are equivalent to the identity permutation, or characterize this equivalence class. Although our results feature familiar integer sequences (e.g., Catalan, Fibonacci, and Tribonacci numbers) and special classes of permutations (layered, connected, and 123-avoiding), some of the sequences
that arise appear to be new.
Original languageEnglish
Article number12.9.1
Number of pages23
JournalJournal of Integer Sequences
Issue number9
Publication statusPublished - 2 Nov 2012


Dive into the research topics of 'Equivalence classes of permutations under various relations generated by constrained transpositions'. Together they form a unique fingerprint.

Cite this