Counting Strings with Given Elementary Symmetric Function
Evaluations I: Strings over Z_{p}
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.
Abstract:
Let a be a string over an alphabet that is a finite ring, R.
The jth elementary symmetric function evaluated at a is
denoted T_{j}(a).
We study the cardinalities of
S_{R}(n;
t_{1},t_{2},...,t_{m}),
the set of of length n strings for which
T_{i}(a) = t_{i}.
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
T_{j}(a),
and hence S_{R};
further, the dependence of T_{j} on the profile is
componentwise periodic.
If R is Z_{p} where p is prime,
then we show the precise
relationship between the profile and
S_{R}(n;
t_{1},t_{2},...,t_{m}), and use
this relationship to efficiently compute S_{R}.

The postscript file is 401,534 bytes,
the pdf file is 228,822 bytes,
the dvi file is ??? bytes.

SIAM J. Discrete Mathematics 17 (2004) 675685.

Original submission September 2002;
response, October 2003; resubmit November 2003, acceptance December
2003.
Back to list of publications.