Journal of Integer Sequences, Vol. 15 (2012), Article 12.9.1

Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions

Steven Linton
Centre for Interdisciplinary Research in Computational Algebra
University of St Andrews
St Andrews, Fife KY16 9AJ
United Kingdom

James Propp
University of Massachusetts
Lowell, MA 01854

Tom Roby
University of Connecticut
Storrs, CT 06269

Julian West
University of Bristol
Bristol BS8 1TW


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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000045 A000073 A000079 A000085 A000108 A000142 A000213 A000930 A001405 A003319 A010551 A052952 A210667 A210668 A210669 A210671 A212417 A212419 A212432 A212433 A212580 A212581 .)

Received June 21 2012; revised version received November 1 2012. Published in Journal of Integer Sequences, November 2 2012.

Return to Journal of Integer Sequences home page