Re: a question of counting

From: David Einstein (Deinst_at_world.std.com)
Date: 03/15/05 

Date: Tue, 15 Mar 2005 09:07:56 -0500

Ed Beroset wrote:
> David Einstein wrote:
>
>> Ed Beroset wrote:
>>
>>> Here's the problem: suppose you have coins that are worth 7, 11 and
>>> 16 units. Assuming that you have an unlimited supply of each
>>> denomination, what is the algorithm by which you can enumerate, in
>>> order, each of the possible sums?
>
> [...]
>
>> Well, it depends on exactly what you are trying to do. If all you
>> want to do is to write a program that enumerates the values, that is
>> easy to do, but I'd need to know how and why you want to do this to
>> give you advice on how to proceed.
>
>
> That's one thing I'd like to have as a result, but I already have a
> brute force program that does this by simply trying all combinations of
> coins and sorting the results by value. I was inspired to look at this
> by a problem (and solutions) given in a relatively recent issue of C/C++
> Users Journal. The problem (paraphrased) was creating a program to
> produce the series of all numbers which are of the form 2^x*3^y*5^z
> where x,y,z are nonnegative integers, in numerical order. It's easy to
> see that this is the same as the problem of x*log(2) + y*log(3) +
> z*log(5) which, for some reason struck me as possibly easier to solve.
> You'll note that my numbers (7,11,16) are scaled integer approximations
> of those logarithms. The longer I pondered, the more I was intrigued by
> the class of problems and their solutions, hence my posting here.
>
>> If you are asking the more interesting question of describing the set
>> of representable values, then you are venturing into the realm of the
>> "Frobenius Problem".
>
>
> Yes, that's exactly what I'm talking about! (I didn't know it by that
> name, but looked it up.) Having a name helps the search process immensely.
>
>> Most papers on the Frobenius problem concern themselves only with
>> finding the largest number not representable, and maybe the number of
>> values not representable. This is more difficult than it looks, with
>> two coins it is simple, with 3 coins there is an algorithm consisting
>> of two applications of the Euclidean algorithm. For n=4 or more coins
>> there is an algorithm of Kannan which will run in polynomial time for
>> fixed n, but is complicated and as far as I know has never been
>> implimented.
>
>
> Very interesting. I'm also interested in knowing if there is a
> generating function for the set of numbers which is representable (or
> conversely for the set of numbers which is not.)

Well, the generating function which counts the number of ways that a
number is representable is very simple f(x)=1/((1-x^7)(1-x^11)(1-x^16))
in your case. Kevin Woods' technique says that the generating function
which merely indicates whether or not a number is representable is
f(x)=(1-x^32-x^44-x^49+x^60+x^65)/((1-x^7)(1-x^11)(1-x^16)) (or
something like that, I may have horked the arithmetic), and something
similar is true in general, though it does get considerably more
complicated sometimes for more than 3 coins. This result never ceases
to amaze me.

If all this interests you, Matthias Beck and Sinai Robbins are writing a
  text aimed at undergraduates (it will be a Springer UTM book) and was
available on Matt's web site last time I checked, but math.sfsu.edu is
not talking to me this morning, so I cannot give a precise URL.

>
>> There is a paper by A. Barvinok and Kevin Woods available on the arXiv
>> that shows that if one creates a power series f(x)=sum_{t is
>> representable} x^t then f(x) has a simple description as a sum of
>> rational functions.
>
>
> Thanks for the specific and helpful reply. As for the name of the field
> to which this problem belongs, it looks like Wolfram classifies this as
> the realm of number theory involving Diophantine equations. Looks
> like I need to find a book on basic number theory and educate myself.
> Thanks for the pointers.
>
> Ed
>