Skip to content

Research at St Andrews

Equivalence classes of permutations under various relations generated by constrained transpositions

Research output: Contribution to journalArticle

Author(s)

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

School/Research organisations

Abstract

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.
Close

Details

Original languageEnglish
Article number12.9.1
Number of pages23
JournalJournal of Integer Sequences
Volume15
Issue number9
Publication statusPublished - 2 Nov 2012

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

Related by journal

  1. Solving computational problems in the theory of word-representable graphs

    Akgün, Ö., Gent, I. P., Kitaev, S. & Zantema, H., 24 Feb 2019, In : Journal of Integer Sequences. 22, 2, 17 p., 19.2.5.

    Research output: Contribution to journalArticle

  2. S-crucial and bicrucial permutations with respect to squares

    Gent, I., Kitaev, S., Konovalov, A., Linton, S. & Nightingale, P., 3 Jun 2015, In : Journal of Integer Sequences. 18, 6, 22 p., 15.6.5.

    Research output: Contribution to journalArticle

  3. Sequences realized by oligomorphic permutation groups

    Cameron, P. J., 1 Dec 2000, In : Journal of Integer Sequences. 3, 1

    Research output: Contribution to journalArticle

ID: 184449270

Top