Periodic Patterns of Signed Shifts - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2013

Periodic Patterns of Signed Shifts

Résumé

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.
Fichier principal
Vignette du fichier
dmAS0174.pdf (353.5 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01229677 , version 1 (17-11-2015)

Identifiants

Citer

Kassie Archer, Sergi Elizalde. Periodic Patterns of Signed Shifts. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.873-884, ⟨10.46298/dmtcs.2350⟩. ⟨hal-01229677⟩

Collections

TDS-MACS
69 Consultations
545 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More