2011/11/16 by Steven J. Linton, Linton, Steven, James Propp +5 · 2 citations
Mathematics · Computer Science · Engineering · #Advanced Combinatorial Mathematics #semigroups and automata theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1111.3920
We consider a large family of equivalence relations on permutations in Sn\nthat generalise those discovered by Knuth in his study of the\nRobinson-Schensted correspondence. In our most general setting, two\npermutations are equivalent if one can be obtained from the other by a sequence\nof pattern-replacing moves of prescribed form; however, we limit our focus to\npatterns where two elements are transposed, subject to the constraint that a\nthird element of a suitable type be in a suitable position. For various\ninstances of the problem, we compute the number of equivalence classes,\ndetermine how many n-permutations are equivalent to the identity permutation,\nor characterise this equivalence class. Although our results feature familiar\ninteger sequences (e.g., Catalan, Fibonacci, and Tribonacci numbers) and\nspecial classes of permutations (layered, connected, and 123-avoiding), some of\nthe sequences that arise appear to be new.\n