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: