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>...

I'm not sure whether your argument above, together with results in the
above link, proves that for all positive integers n, f(n,k) is a
polynomial in k. Does it?

quasi
.

Relevant Pages

  • Re: Possible results from three variables
    ... For positive integers n,k, let fbe the number of possible ... subgroup of R^m, i.e. a lattice. ... Let K be the polytope ... polynomials in k with rational coefficients. ...
    (sci.math)
  • Re: No Putnam spoilers please!
    ... Canada in 2009 today on Saturday 5 December, ... Also some students may take exams on Sunday because of ... The balanced polynomials of ...
    (sci.math)
  • Re: Possible results from three variables
    ... For positive integers n,k, let fbe the number ... since they have combinatorical meaning in a similar way to the original question here. ... and also some kind of Ehrhart polynomials, but ill stick with euler at first sight. ...
    (sci.math)
  • Re: Possible results from three variables
    ... For positive integers n,k, let fbe the number of possible ... fixed polytope. ... A quick search turns up Ehrhart polynomials ... subgroup of R^m, i.e. a lattice. ...
    (sci.math)
  • Re: ranges of integer polynomials
    ... Note that if A is a set of positive integers, ... but have the same recursive ranges ... which of these other, "hyperbolic", polynomials ... This gets at the heart of the undecidability issue. ...
    (sci.math)