Adjacent transformations in permutations
International audience 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...
Published in: | Discrete Mathematics & Theoretical Computer Science |
---|---|
Main Authors: | , , |
Other Authors: | , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://inria.hal.science/hal-01215071 https://inria.hal.science/hal-01215071/document https://inria.hal.science/hal-01215071/file/dmAO0167.pdf https://doi.org/10.46298/dmtcs.2951 |
id |
ftunivparis:oai:HAL:hal-01215071v1 |
---|---|
record_format |
openpolar |
spelling |
ftunivparis:oai:HAL:hal-01215071v1 2024-05-12T08:05:50+00:00 Adjacent transformations in permutations Pierrot, Adeline Rossin, Dominique West, Julian Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Laboratoire d'informatique de l'École polytechnique Palaiseau (LIX) École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS) Heilbronn Institute for Mathematical Research University of Bristol Bristol Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel Reykjavik, Iceland 2011 https://inria.hal.science/hal-01215071 https://inria.hal.science/hal-01215071/document https://inria.hal.science/hal-01215071/file/dmAO0167.pdf https://doi.org/10.46298/dmtcs.2951 en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2951 hal-01215071 https://inria.hal.science/hal-01215071 https://inria.hal.science/hal-01215071/document https://inria.hal.science/hal-01215071/file/dmAO0167.pdf doi:10.46298/dmtcs.2951 info:eu-repo/semantics/OpenAccess ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://inria.hal.science/hal-01215071 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.765-776, ⟨10.46298/dmtcs.2951⟩ 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] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftunivparis https://doi.org/10.46298/dmtcs.2951 2024-04-16T03:13:42Z International audience 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. Nous étudions dans cet article les classes d'équivalence sur les permutations obtenues en remplaçant un ensemble consécutif de valeurs par ces même valeurs mais dans un ordre différent. Nous étudions l'ensemble des remplacements possibles de longueur 3 et pour chacun d'entre eux caractérisons et énumérons les permutations de la classe de l'identité. Pour certains ensembles, nous calculons de même le nombre de classes d'équivalence. Conference Object Iceland Université de Paris: Portail HAL Discrete Mathematics & Theoretical Computer Science DMTCS Proceeding Proceedings |
institution |
Open Polar |
collection |
Université de Paris: Portail HAL |
op_collection_id |
ftunivparis |
language |
English |
topic |
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] |
spellingShingle |
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] Pierrot, Adeline Rossin, Dominique West, Julian Adjacent transformations in permutations |
topic_facet |
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] |
description |
International audience 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. Nous étudions dans cet article les classes d'équivalence sur les permutations obtenues en remplaçant un ensemble consécutif de valeurs par ces même valeurs mais dans un ordre différent. Nous étudions l'ensemble des remplacements possibles de longueur 3 et pour chacun d'entre eux caractérisons et énumérons les permutations de la classe de l'identité. Pour certains ensembles, nous calculons de même le nombre de classes d'équivalence. |
author2 |
Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Laboratoire d'informatique de l'École polytechnique Palaiseau (LIX) École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS) Heilbronn Institute for Mathematical Research University of Bristol Bristol Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel |
format |
Conference Object |
author |
Pierrot, Adeline Rossin, Dominique West, Julian |
author_facet |
Pierrot, Adeline Rossin, Dominique West, Julian |
author_sort |
Pierrot, Adeline |
title |
Adjacent transformations in permutations |
title_short |
Adjacent transformations in permutations |
title_full |
Adjacent transformations in permutations |
title_fullStr |
Adjacent transformations in permutations |
title_full_unstemmed |
Adjacent transformations in permutations |
title_sort |
adjacent transformations in permutations |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://inria.hal.science/hal-01215071 https://inria.hal.science/hal-01215071/document https://inria.hal.science/hal-01215071/file/dmAO0167.pdf https://doi.org/10.46298/dmtcs.2951 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://inria.hal.science/hal-01215071 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.765-776, ⟨10.46298/dmtcs.2951⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2951 hal-01215071 https://inria.hal.science/hal-01215071 https://inria.hal.science/hal-01215071/document https://inria.hal.science/hal-01215071/file/dmAO0167.pdf doi:10.46298/dmtcs.2951 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.46298/dmtcs.2951 |
container_title |
Discrete Mathematics & Theoretical Computer Science |
container_volume |
DMTCS Proceeding |
container_issue |
Proceedings |
_version_ |
1798848211924811776 |