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...
Main Authors: | , , |
---|---|
Other Authors: | , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01215071 https://hal.inria.fr/hal-01215071/document https://hal.inria.fr/hal-01215071/file/dmAO0167.pdf |
id |
ftccsdartic:oai:HAL:hal-01215071v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-01215071v1 2023-05-15T16:49:27+02: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) Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X) Heilbronn Institute for Mathematical Research University of Bristol Bristol Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel Reykjavik, Iceland 2011 https://hal.inria.fr/hal-01215071 https://hal.inria.fr/hal-01215071/document https://hal.inria.fr/hal-01215071/file/dmAO0167.pdf en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS hal-01215071 https://hal.inria.fr/hal-01215071 https://hal.inria.fr/hal-01215071/document https://hal.inria.fr/hal-01215071/file/dmAO0167.pdf 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://hal.inria.fr/hal-01215071 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.765-776 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 ftccsdartic 2021-11-21T03:02:19Z 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 Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
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) Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X) 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://hal.inria.fr/hal-01215071 https://hal.inria.fr/hal-01215071/document https://hal.inria.fr/hal-01215071/file/dmAO0167.pdf |
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://hal.inria.fr/hal-01215071 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.765-776 |
op_relation |
hal-01215071 https://hal.inria.fr/hal-01215071 https://hal.inria.fr/hal-01215071/document https://hal.inria.fr/hal-01215071/file/dmAO0167.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1766039582862737408 |