Cyclic permutations realized by signed shifts

The periodic (ordinal) patterns of a map are the permutations realized by the relative order of the points in its periodic orbits. We give a combinatorial characterization of the periodic patterns of an arbitrary signed shift, in terms of the structure of the descent set of a certain cyclic permutation associated to the pattern. Signed shifts are an important family of one-dimensional dynamical systems that includes shift maps and the tent map as particular cases. Defined as a function on the set of infinite words on a finite alphabet, a signed shift deletes the first letter and, depending on its value, possibly applies the complementation operation on the remaining word. For shift maps, reverse shift maps, and the tent map, we give exact formulas for their number of periodic patterns. As a byproduct of our work, we recover results of Gessel-Reutenauer and Weiss-Rogers and obtain new enumeration formulas for pattern-avoiding cycles.

Keywords

periodic pattern, signed shift, cyclic permutation, descent, pattern avoidance, reverse shift, periodic orbit

2010 Mathematics Subject Classification

Primary 05A15. Secondary 37M10, 94A55.

Full Text (PDF format)

Published 12 February 2014