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.

Keywords

• periodic pattern
• signed shift
• cyclic permutation
• descent
• pattern avoidance.
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]