zbMATH — the first resource for mathematics

Equivalence classes of permutations under various relations generated by constrained transpositions. (English) Zbl 1292.05013
Summary: 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.

05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
Full Text: EMIS arXiv