Counting Strings with Given Elementary Symmetric Function Evaluations II: Circular Strings
C. Robert Miers, Frank Ruskey · SIAM Journal on Discrete Mathematics · 2004
Let $\alpha$ be a string over an alphabet that is a finite ring, R. The kth elementary symmetric function evaluated at $\alpha$ is denoted $T_k(alpha)$. In a companion paper we studied the properties of $\mathbf{S}_R(n;\tau_1,\tau_2,\ldots,\tau_k)$, the set of length n strings for which $T_i(\alpha) = \tau_i$. Here we consider the set, $\mathbf{L}_R(n;\tau_1,\tau_2,\ldots,\tau_k)$, of equivalence classes under rotation of aperiodic strings in $\mathbf{S}_R(n;\tau_1,\tau_2,\ldots,\tau_k)$, sometimes called Lyndon words. General formulae are established and then refined for the cases where R is the ring of integers $\Z{q}$ or the finite field $\F{q}$.