Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01229677
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:19:46 AM
Last modification on : Wednesday, June 26, 2019 - 4:36:03 PM
Long-term archiving on: : Thursday, February 18, 2016 - 11:36:19 AM

File

dmAS0174.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229677, version 1

Collections

Citation

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. ⟨hal-01229677⟩

Share

Metrics

Record views

110

Files downloads

647