Skip to content

Research at St Andrews

Equivalence relations of permutations generated by constrained transpositions

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

Author(s)

Stephen Linton, James Propp, Tom Roby, Julian West

School/Research organisations

Abstract

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.

Close

Details

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
Pages909-920
Number of pages12
Publication statusPublished - 2010

Publication series

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

    Research areas

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

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. GAP – Groups, Algorithms, and Programming, Version 4.10.2

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 19 Jun 2019

    Research output: Non-textual formSoftware

  2. GAP – Groups, Algorithms, and Programming, Version 4.10.1

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 23 Feb 2019

    Research output: Non-textual formSoftware

  3. GAP – Groups, Algorithms, and Programming, Version 4.10.0

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 1 Nov 2018

    Research output: Non-textual formSoftware

  4. GAP – Groups, Algorithms, and Programming, Version 4.9.3

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 5 Sep 2018

    Research output: Non-textual formSoftware

  5. PatternClass Version 2.4.2: A permutation pattern class package (GAP package)

    Hoffmann, R., Linton, S. & Albert, M., 24 Jul 2018

    Research output: Non-textual formSoftware

ID: 184449329

Top