Permutations realized by signed shifts
Kassie Archer · 2014
In this thesis, we characterize and enumerate the permutations which are realized by the orbits of signed shifts, a family of discrete dynamical systems on words. The permutations, which are called patterns of the signed shifts, are given by the relative order of the iterates of each word with respect to the dynamical system. We obtain a combinatorial characterization of these patterns in terms of a bijection, which we use to provide bounds on the size of the set of patterns of the signed shift. When we restrict to the periodic words in the dynamical system, we can use this characterization to prove purely combinatorial results. This includes enumerating the set of cyclic permutations in certain pattern-avoiding classes, which we call σ-classes. We also present some work toward enumerating the set of cyclic permutations that avoid a single pattern of length 3. Finally, we show how to use this characterization to prove a formula for a character of the symmetric group and discuss interesting consequences of this formula for the distribution of the descent set on the set of cyclic permutations.