Cyclic permutations realized by signed shifts
By Kassie Archer, Sergi Elizalde. 2013
48 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
View Paper: https://www.semanticscholar.org/paper/adfe5f16384c3704c78587816ab695b962466dc2
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
Citations in the corpus
- A survey of consecutive patterns in permutations (2015, background): “Long before this concept was introduced and systematically studied in [35] by Elizalde and Noy, there had been implicit appearances of consecutive patterns in the combinatorics literature.”