DMTCS Proceedings, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)

Font Size:  Small  Medium  Large

Adjacent transformations in permutations

Adeline Pierrot, Dominique Rossin, Julian West


We continue a study of the equivalence class induced on Sn 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.
Résumé. 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.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional