DMTCS Proceedings, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

Font Size:  Small  Medium  Large

Periodic Patterns of Signed Shifts

Kassie Archer, Sergi Elizalde


The periodic patterns of a map are the permutations realized by the relative order of the points in its periodic orbits. We give a combinatorial description of the periodic patterns of an arbitrary signed shift, in terms of the structure of the descent set of a certain transformation of the pattern. Signed shifts are an important family of one-dimensional dynamical systems. For particular types of signed shifts, namely shift maps, reverse shift maps, and the tent map, we give exact enumeration formulas for their periodic patterns. As a byproduct of our work, we recover some results of Gessel and Reutenauer and obtain new results on the enumeration of pattern-avoiding cycles.
Résumé. Les motifs périodiques d'une fonction sont les permutations réalisées par l'ordre relatif des points dans ses orbites périodiques. Nous donnons une description combinatoire des motifs périodiques d'un shift signé arbitraire, en termes de la structure de l'ensemble des descentes d'une certaine transformation du motif. Les shifts signés sont une familie importante de systèmes dynamiques unidimensionnels. Pour des types particuliers de shifts signés, comme les fonctions de shift, les fonctions de shift inversées, et la fonction de tente, nous donnons des formules exactes pour l'énumération de leurs motifs périodiques. Comme sous-produit de notre travail, nous retrouvons des résultats de Gessel et Reutenauer et obtenons de nouveaux résultats sur l'énumération de cycles qui évitent certain motifs.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional