Stephen Linton ; James Propp ; Tom Roby ; Julian West - Equivalence Relations of Permutations Generated by Constrained Transpositions

dmtcs:2841 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010) - https://doi.org/10.46298/dmtcs.2841
Equivalence Relations of Permutations Generated by Constrained TranspositionsArticle

Authors: Stephen Linton 1; James Propp 2; Tom Roby 3; Julian West 4

  • 1 Centre for Interdisciplinary Research in Computational Algebra [St Andrews]
  • 2 Department of Mathematics [Lowell]
  • 3 University of Connecticut
  • 4 University of Bristol [Bristol]

We consider a large family of equivalence relations on permutations in $S_n$ 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.


Volume: DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: pattern-avoiding permutations,connected permutations,permutation patterns,equivalence classes,Knuth relations,integer sequences,Catalan numbers,layered permutations,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

1 Document citing this article

Consultation statistics

This page has been seen 196 times.
This article's PDF has been downloaded 391 times.