Mathematics – Combinatorics
Scientific paper
2011-11-16
Mathematics
Combinatorics
21 pages, submitted
Scientific paper
We consider a large family of equivalence relations on permutations in Sn that generalise 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 characterise 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.
Linton Steven
Propp James
Roby Tom
West Julian
No associations
LandOfFree
Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-69660