Equivalence relations of permutations generated by constrained transpositions

Stephen Linton, James Propp, Tom Roby, Julian West

Research output: Chapter in Book/Report/Conference proceedingOther contribution

2 Citations (Scopus)


We consider a large family of equivalence relations on permutations in Sn that generalise 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, conditional upon the presence of a third element of suitable value and location. For some relations of this type, we compute the number of equivalence classes, determine how many n-permutations are equivalent to the identity permutation, or characterise this equivalence class. Although our results include 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
Title of host publication22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)
Place of PublicationNancy
PublisherAssoc. Discrete Math. Theor. Comput. Sci., Nancy
Number of pages12
Publication statusPublished - 2010

Publication series

NameDiscrete Math. Theor. Comput. Sci. Proc., AN
PublisherAssoc. Discrete Math. Theor. Comput. Sci., Nancy


  • Permutation patterns
  • Equivalence classes
  • Knuth relations
  • Integer sequences
  • Catalan numbers
  • Layered permutations
  • Connected permutations
  • Pattern-avoiding permutations


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

Cite this