Equivalence classes of permutations under various relations generated by constrained transpositions
From MaRDI portal
Abstract: 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.
Recommendations
- Equivalence relations of permutations generated by constrained transpositions
- Counting permutations modulo pattern-replacement equivalences for three-letter patterns
- Equivalence classes of permutations modulo excedances
- Equivalence classes of permutations modulo replacements between 123 and two-integer patterns
- Adjacent transformations in permutations
Cited in
(14)- From Hertzsprung's problem to pattern-rewriting systems
- New results on families of pattern-replacement equivalences
- Equivalence classes of permutations modulo excedances
- Involution words. II: Braid relations and atomic structures
- An equivalence relation on the symmetric group and multiplicity-free flag \(h\)-vectors
- Representing permutations with few moves
- Adjacent transformations in permutations
- Equivalence classes of permutations modulo descents and left-to-right maxima
- Перестановочные решетки отношений эквивалентности на декартовых произведениях и согласованные с ними системы уравнений. II
- scientific article; zbMATH DE number 4021204 (Why is no real title available?)
- Counting permutations modulo pattern-replacement equivalences for three-letter patterns
- Equivalence classes of permutations modulo replacements between 123 and two-integer patterns
- Equivalence relations of permutations generated by constrained transpositions
- Counting the nontrivial equivalence classes of \(S_n\) under \(\{1234, 3412\}\)-pattern-replacement
This page was built for publication: Equivalence classes of permutations under various relations generated by constrained transpositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404260)
