Adeline Pierrot ; Dominique Rossin ; Julian West - Adjacent transformations in permutations

dmtcs:2951 - Discrete Mathematics & Theoretical Computer Science, January 1, 2011, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) - https://doi.org/10.46298/dmtcs.2951
Adjacent transformations in permutationsArticle

Authors: Adeline Pierrot 1; Dominique Rossin 2; Julian West 3

  • 1 Laboratoire d'informatique Algorithmique : Fondements et Applications
  • 2 Laboratoire d'informatique de l'École polytechnique [Palaiseau]
  • 3 Heilbronn Institute for Mathematical Research

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.


Volume: DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
Section: Proceedings
Published on: January 1, 2011
Imported on: January 31, 2017
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]

2 Documents citing this article

Consultation statistics

This page has been seen 290 times.
This article's PDF has been downloaded 205 times.