Periodic Patterns of Signed Shifts

Abstract : The periodic patterns of a map are the permutations realized by the relative order of the points in its periodic orbits. We give a combinatorial description of the periodic patterns of an arbitrary signed shift, in terms of the structure of the descent set of a certain transformation of the pattern. Signed shifts are an important family of one-dimensional dynamical systems. For particular types of signed shifts, namely shift maps, reverse shift maps, and the tent map, we give exact enumeration formulas for their periodic patterns. As a byproduct of our work, we recover some results of Gessel and Reutenauer and obtain new results on the enumeration of pattern-avoiding cycles.
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.873-884, 2013, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01229677
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:19:46
Dernière modification le : jeudi 23 novembre 2017 - 15:34:02
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:36:19

Fichier

dmAS0174.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01229677, version 1

Collections

Citation

Kassie Archer, Sergi Elizalde. Periodic Patterns of Signed Shifts. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.873-884, 2013, DMTCS Proceedings. 〈hal-01229677〉

Partager

Métriques

Consultations de la notice

69

Téléchargements de fichiers

150