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