Re: Possible results from three variables

On Thu, 12 Jul 2007 19:23:59 -0500, Robert Israel
<israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

quasi <quasi@xxxxxxxx> writes:

On Thu, 12 Jul 2007 07:25:37 -0000, "bakpao@xxxxxxxxx"
<bakpao@xxxxxxxxx> wrote:

Given three variables, say x, y, z with each variable being an integer
from 1 to 10, how many possible values are there from the equation of
x * y * z? The quickest and incorrect answer is 1000 (from 10x10x10).
This is wrong because some of the combinations actually the same, e.g.
1*2*4 = 1*4*2 = 4*1*2 = 1*8*1. Doing 10C3 is also wrong.

Is there any formula that we can use to find out the number of
possibilities for the different integer range (e.g. 1 - 5 or 1 - 8)?

For positive integers n,k, let f(n,k) be the number of possible
products of k integers from the range 1 to n inclusive.

It's obvious that f(1,k)=1 for all positive integers k.

It's also obvious that f(n,1)=n for all positive integers n,

For a fixed positive integer n, it appears that f(n,k) is always a
polynomial in k.

Very interesting...

You can think of it this way. Suppose p_1, ..., p_m are the primes
<= n. Each possible product can be represented uniquely in the form
y = p_1^y_1 ... p_m^y_m where y_1 ... y_m are nonnegative integers. If
a_{ix} is the power of p_i appearing in the representation of x and
y = 1^{x_1} 2^{x_2} ... n^{x_n} is one of the products we have
p_i = sum_{j=1}^n a_{ij} x_j with sum_{i=1}^n x_i = k. Thus f(n,k) is
the cardinality of T(K_k) where T is the linear map of R^n to R^m
corresponding to the m x n matrix (a_{ij}) and
K_k = {(x_1,...,x_n) in Z^n: all x_i >= 0, sum_i x_i = k}.
Essentially we're trying to count the lattice points in the dilations of a
fixed polytope.
A quick search turns up Ehrhart polynomials
<http://mathworld.wolfram.com/EhrhartPolynomial.html>...

Yes -- the interpretation as a count of lattice points makes sense.

The volume could probably be estimated by Monte Carlo methods and
that, together with some analysis of the "eccentricity" of the
boundary, might at least lead to good estimates.

Alternatively, the interpretation you describe can perhaps allow the
problem to be recast as an integer programming problem. Then again,
maybe not. We are not trying for feasibility or optimization. We want
to count the number of feasible solutions. Thus, integer programming
methods may not help -- I'm not sure.

quasi
.