What’s common between changing dollar into coins, counting “lucky tickets” and degeneracy of the energy levels of quantum harmonic oscillator in 3D?

All of these subjects can be approached with *generating function* technique.

# Generating Functions: Part 1. Changing Dollar.

In the first post in the series we cover “change dollar” problem. It is one problem in a collection of three seemingly unrelated (but well known) ones, which we will discuss. The problems are tightly connected, as it turns out, if treated from generating functions approach.

## Changing Dollar

**Problem 1.** [1] In how many ways can you change one dollar bill into coins if you have necessary supply of coins worth 1, 5, 10, 25 and 50 cents?

Example: 1+1+…+1 (100 times) is one way; adding 95 cents and one nickel 1+1+…+1 + 5 is another way, but having 5+1+…+1 (nickel and then cents) is considered to be the same as the previous one.

When trying to solve this problem, brute force application would not be too helpful. Even if with some luck and patience it would possible to enumerate solutions, it would be hard to extend this to other similar problems.

General solution comes from using *generating function. *Consider formal product:

(1) ……………

(2) ……

Manual calculation of the value of is still laborious so small Python class for manipulating polynomials comes in handy:

"""Minimal and straightfoward implementation of symbolic polynomials to solve 'change dollar' problem with generating functions. """ class Polynomial: """Holds an array of coefficients, all calculations are limiated to maxPower, i.e. all coefficients higher than maxPower are ignored.""" def __init__(self, c, maxPower): """c - value to which all coefficients will be initialized to, maxPower is actually number of coefficents, so for quadratic polynomial its value should be 3.""" self. maxPower = maxPower self.coefficients = [c]*maxPower def substitutePower(self, multiplier): """ Substitutes variable x with x^multiplier.""" newCoefficients = [0]*self. maxPower i = 0 while i*multiplier < self.maxPower: newCoefficients[i*multiplier] = self.coefficients[i] i+=1 self.coefficients = newCoefficients def mult(self, other): """ Multiplies in place Polynomial with the other Polynomial.""" newCoefficients = [0]*self. maxPower for i in range(self. maxPower): for j in range(self. maxPower): k = i+j if k < self. maxPower: newCoefficients[k] += self.coefficients[i]*other.coefficients[j] self.coefficients = newCoefficients

And the computation would look like:

p1 = Polynomial(1, 101) p5 = Polynomial(1, 101) p5.substitutePower(5) p10 = Polynomial(1, 101) p10.substitutePower(10) p25 = Polynomial(1, 101) p25.substitutePower(25) p50 = Polynomial(1, 101) p50.substitutePower(50) p50.mult(p25) p50.mult(p10) p50.mult(p5) p50.mult(p1) print "A_100 = ",p50.coefficients[100]

The output of this calculation equals to **292**.

As a side note related to Russian edition of the same book [1], the number of ways to change ruble is considerably higher. The available coins worth 1,2,5,10,20 and 50 (six total vs. five in the original version of the problem). The answer in this case is **4562**. (I gave up on obtaining numerical answer for this problem on paper. Actually, I don’t know anyone who managed all the way through without help of a computer for the six coins case.)

Interestingly enough, problem 2 in the book [1] works as a hint for the problem 1 stated above. It asks to calculate number of non-negative integer solutions for Diofantine equation with non-negative right hand side:

(3)

and directly points at existence of series (2) with rational representation as in the second line of (1).

## References

[1] G. Polya, G. Szegö, “Problems and Theorems in Analysis I: Series, Integral Calculus, Theory of Functions”, Springer (2004), 414 pages.