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.
Abstract:
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.
-
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) 675-685.
-
Original submission September 2002;
response, October 2003; resubmit November 2003, acceptance December
2003.
Back to list of publications.