Kassie Archer ; Sergi Elizalde - Periodic Patterns of Signed Shifts

dmtcs:2350 - Discrete Mathematics & Theoretical Computer Science, January 1, 2013, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) - https://doi.org/10.46298/dmtcs.2350
Periodic Patterns of Signed ShiftsArticle

Authors: Kassie Archer 1; Sergi Elizalde ORCID1

  • 1 Department of Mathematics [Dartmouth]

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.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: periodic pattern,signed shift,cyclic permutation,descent,pattern avoidance.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Pattern avoidance in dynamical systems; Funder: National Science Foundation; Code: 1001046

Consultation statistics

This page has been seen 244 times.
This article's PDF has been downloaded 232 times.