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

Font Size:  Small  Medium  Large

Counting strings over ℤ2d

C. R. Miers, F. Ruskey

Abstract


Abstract. Let α be a string over q, where q = 2d. The j-th elementary symmetric function evaluated at α is denoted jα. We study the cardinalities Sq(m;τ1,τ2,…,τt) of the set of length m strings for which iα = τi. The profile k(α) = ⟨k1,k2,…,kq-1 ⟩ of a string α is the sequence of frequencies with which each letter occurs. The profile of α determines jα, and hence Sq. Let hn : 2n+d-1(q-1) ↦2d[z] z2n be the map that takes k(α) 2n+d-1 to the polynomial 1+1α z+ 2α z2 + ⋯+ 2n-1α z2n-1. We show that hn is a group homomorphism and establish necessary conditions for membership in the kernel for fixed d. The kernel is determined for d = 2,3. The range of hn is described for d = 2. These results are used to efficiently compute S4(m;τ1,τ2,…,τt) for d = 2 and the number of complete factorizations of certain polynomials. Résumé. Soit α un mot sur ℤq, où q=2d. La j-ième fonction symmétrique élémentaire évaluée à α est dénotée ej(α). Nous étudions les cardinalités Sq(m;τ1,τ2,…,τt) de l'ensemble des mots de longueur m pour lesquels ei(α)=τi. Le profil k(α)= ⟨k1,k2,…,kq-1 ⟩ d'un mot α est la suite de fréquences d'apparition de chaque lettre. Le profil de α détermine ej (α) et donc Sq. Soit hn :ℤ(q-1)2n+d-1 ↦ℤ2d[z] mod z2n la fonction qui associe à k(α) mod 2n+d-1 le polynôme 1+e1(α)z+e2(α)z2+⋯+e2n -1(α)z2n -1. Nous démontrons que hn est un homomorphisme de groupe et nous établissons des conditions nécessaires à l'appartenance au noyau pour un d fixé. Le noyau est déterminé pour d=2,3. L'image de hn est décrite pour d=2. Ces résultats sont utilisés pour calculer de manière efficace S4 (m;τ1,τ2,…,τt) pour d=2 ainsi que le nombre de factorisations complètes de certains polynômes.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional