Counting Strings with Given Elementary Symmetric Function Evaluations I: Strings over Zp with p Prime

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
C. Robert Miers, Department of Mathematics and Statistics, University of Victoria, Canada.


Let a be a string over an alphabet that is a finite ring, R. The j-th elementary symmetric function evaluated at a is denoted Tj(a). We study the cardinalities of SR(n; t1,t2,...,tm), the set of of length n strings for which Ti(a) = ti. The profile of a string a is the sequence of frequencies with which each letter occurs. If R is commutative, then the profile of a determines Tj(a), and hence SR; further, the dependence of Tj on the profile is componentwise periodic. If R is Zp where p is prime, then we show the precise relationship between the profile and SR(n; t1,t2,...,tm), and use this relationship to efficiently compute SR.

Back to list of publications.