zbMATH — the first resource for mathematics

Equivalence relations of permutations generated by constrained transpositions. (English. French summary) Zbl 1374.05008
Proceedings of the 22nd annual international conference on formal power series and algebraic combinatorics, FPSAC 2010, San Francisco, USA, August 2–6, 2010. Nancy: The Association. Discrete Mathematics & Theoretical Computer Science (DMTCS). Discrete Mathematics and Theoretical Computer Science. Proceedings, 909-920 (2010).
Summary: We consider a large family of equivalence relations on permutations in $$S_n$$ 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, 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 $$n$$-permutations 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 123-avoiding), some of the sequences that arise appear to be new.
For the entire collection see [Zbl 1198.05002].

MSC:
 05A05 Permutations, words, matrices
Full Text: