Making Lots Of Change


John D Cook’s Algebra Fact of the Day points to a pair of algorithms about making change. Specifically these are about how many ways there are to provide a certain amount of change using United States coins. By that he, and the algorithms, mean 1, 5, 10, 25, and 50 cent pieces. I’m not sure if 50 cent coins really count, since they don’t circulate any more than dollar coins do. Anyway, if you want to include or rule out particular coins it’s clear enough how to adapt things.

What surprised me was a simple algorithm, taken from Ronald L Graham, Donald E Knuth, and Oren Patashnik’s Concrete Mathematics: A Foundation For Computer Science to count the number of ways to make a certain amount of change. You start with the power series that’s equivalent to this fraction:

\frac{1}{\left(1 - z\right)\cdot\left(1 - z^{5}\right)\cdot\left(1 - z^{10}\right)\cdot\left(1 - z^{25}\right)\cdot\left(1 - z^{50}\right)}

A power series is a polynomial. The power series for \frac{1}{1 - z} , for example, is 1 + z + z^2 + z^3 + z^4 + \cdots ... and carries on forever like that. But if you choose a number between minus one and positive one, and put that in for z in either \frac{1}{1 - z} or in that series 1 + z + z^2 + z^3 + z^4 + \cdots ... you’ll get the same number. (If z is not between minus one and positive one, it doesn’t. Don’t worry about it. For what we’re doing we will never need any z.)

The power series for that big fraction with all the kinds of change in it is more tedious to work out. You’d need the power series for \frac{1}{1 - z} and \frac{1}{1 - z^5} and \frac{1}{1 - z^{10}} and so on, and to multiply all those series together. And yes, that’s multiplying infinitely long polynomials together, which you might reasonably expect will take some time.

You don’t need to, though. All you really want is a single term in this series. To tell how many ways there are to make n cents of change, look at the coefficient, the number, in front of the zn term. That’s the number of ways. So while this may be a lot of work, it’s not going to be hard work, and it’s going to be finite. You only have to work out the products that give you a zn power. That will take planning and preparation to do correctly, but that’s all.

Advertisements

Author: Joseph Nebus

I was born 198 years to the day after Johnny Appleseed. The differences between us do not end there.

2 thoughts on “Making Lots Of Change”

  1. Another cool thing about this is that you can get z^n term by computing the complex contour integral:
    http://math.stackexchange.com/questions/338228/what-is-the-significance-of-this-theorem-coefficients-of-power-series-as-integr
    And if you are not willing to do the analytic computation, you can let the computer do a Riemann sum approximation and thus get the coefficient you are looking for. As we already know that the result is an integer, an error less than .5 is sufficient.

    Liked by 1 person

Please Write Something Good

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s