Séminaire Lotharingien de Combinatoire, 78B.49 (2017), 12 pp.

Kassie Archer, Sergi Elizalde and Katherine Moore

Patterns of Negative Shifts and Signed Shifts

Abstract. Given a function f from a linearly ordered set X to itself, we say that a permutation π is an allowed pattern of f if the relative order of the first n iterates of f beginning at some x in X is given by π. We give a characterization of the allowed patterns of signed shifts in terms of monotone runs of a certain transformation of π, which completes and simplifies the original characterization given by Amigó. Signed shifts, which are generalizations of the shift map where some slopes are allowed to be negative, are particularly well-suited to a combinatorial analysis. In the special case where all the slopes are negative, we give an exact formula for the number of allowed patterns. Finally, we obtain a combinatorial derivation of the topological entropy of signed shifts.

Received: November 14, 2016. Accepted: February 17, 2017. Final version: April 1, 2017.

The following versions are available: