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