Projects per year
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 RobinsonSchensted correspondence. In our most general setting, two permutations are equivalent if one can be obtained from the other by a sequence of patternreplacing 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 npermutations 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 123avoiding), some of the sequences
that arise appear to be new.
that arise appear to be new.
Original language  English 

Article number  12.9.1 
Number of pages  23 
Journal  Journal of Integer Sequences 
Volume  15 
Issue number  9 
Publication status  Published  2 Nov 2012 
Fingerprint
Dive into the research topics of 'Equivalence classes of permutations under various relations generated by constrained transpositions'. Together they form a unique fingerprint.Projects
 1 Finished

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Linton, S. A., Gent, I. P., Leonhardt, U., Mackenzie, A., Miguel, I. J., Quick, M. & Ruskuc, N.
1/09/05 → 31/08/10
Project: Standard