Adjacent transformations in permutations

Abstract

We continue a study of the equivalence class induced on $S_n$ when one is permitted to replace a consecutive set of elements in a permutation with the same elements in a different order. For each possible set of allowed replacements, we characterise and/or enumerate the set of permutations reachable from the identity. In some cases we also count the number of equivalence classes.

Keywords

• permutation patterns
• equivalence classes
• integer sequences
• catalan numbers
• sorting permutations
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]