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.

Abstract:

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 T_k(a). In a companion paper we studied the properties of S_R ( n; t₁,t₂,...,t_k ), the set of of length n strings for which T_i ( a ) = t_i. Here we consider the set, L_R ( n; t₁,t₂,...,t_k ), of equivalence classes under rotation of aperiodic strings in S_R ( n; t₁,t₂,...,t_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 Z_q.

The postscript file is 415,007 bytes, The postscript file is 241,704 bytes, the dvi file is ??? bytes.
SIAM J. Discrete Mathematics, 18 (2004) 71-82.
Final acceptance February 17, 2004.

Back to list of publications.