Counting Strings with Given Elementary Symmetric Function Evaluations I: Strings over \boldmath$\mathbbZ_p$ with p Prime
C. Robert Miers, Frank Ruskey · SIAM Journal on Discrete Mathematics · 2004
Let $\alpha$ be a string over $\mathbb{Z}_p$ with p prime. The jth elementary symmetric function evaluated at $\alpha$ is denoted $T_j(\alpha)$. We study the cardinalities $S_p(n;\tau_1,\tau_2,\ldots,\tau_t)$ of the set of length n strings for which $T_i(\alpha) = \tau_i$. The \emph{profile} $\langle k_0,k_1,\ldots,k_{p-1} \rangle$ of a string $\alpha$ is the sequence of frequencies with which each letter occurs. The profile of $\alpha$ determines $T_j(\alpha)$, and hence $S_p$. Let $f_n : \mathbb{Z}_{p^n}^{p-1} \mapsto obreak \mathbb{Z}_p^{p^n-1}$ be the map that takes $\langle k_0,k_1,\ldots,k_{p-1} \rangle \bmod {p^n}$ to $(T_1,T_2,\ldots,T_{p^n-1}) \bmod p$. We show that $f_n$ is well defined and injective and show how to efficiently determine its range. These results are used to efficiently compute $S_p(n;\tau_1,\tau_2,\ldots,\tau_t)$.