Counting Strings with Given Elementary Symmetric Function Evaluations II: Circular Strings

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 k-th elementary symmetric function evaluated at a is denoted Tk(a). In a companion paper we studied the properties of SR ( n; t1,t2,...,tk ), the set of of length n strings for which Ti ( a ) = ti. Here we consider the set, LR ( n; t1,t2,...,tk ), of equivalence classes under rotation of aperiodic strings in SR ( n; t1,t2,...,tk ), sometimes called Lyndon words. General formulae are established, and then refined for the cases where R is the ring of integers Zq or the finite field Zq.

Back to list of publications.