Projects per year
Abstract
We consider a large family of equivalence relations on permutations in S_{n} that generalise 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, 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 npermutations 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 123avoiding), some of the sequences that arise appear to be new.
Original language  English 

Title of host publication  22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010) 
Place of Publication  Nancy 
Publisher  Assoc. Discrete Math. Theor. Comput. Sci., Nancy 
Pages  909920 
Number of pages  12 
Publication status  Published  2010 
Publication series
Name  Discrete Math. Theor. Comput. Sci. Proc., AN 

Publisher  Assoc. Discrete Math. Theor. Comput. Sci., Nancy 
Keywords
 Permutation patterns
 Equivalence classes
 Knuth relations
 Integer sequences
 Catalan numbers
 Layered permutations
 Connected permutations
 Patternavoiding permutations
Fingerprint
Dive into the research topics of 'Equivalence relations of permutations 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