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) $F(x)=(1+x+x^2+$ … $)(1+x^5+x^{10}+$ … $)(1+x^{10}+x^{20}+$ … $)(1+x^{25}+x^{50}+$ … $)(1+x^{50}+x^{100}+$ … $)$

$=\frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})}$

Each term in this product corresponds to sum of powers of $x$ which are multiples of the coin’s worth. It is easy to see that after opening brackets and calculating coefficient $A_{100}$ at $x^{100}$ we will get the answer to the problem:

(2) $F(x)=\sum_{i=0}^{\infty}A_i x^i=$ … $+A_{100} x^{100}+$ …

Manual calculation of the value of $A_{100}$ 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) $x+5y+10z+25u+50v = n$

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.

3DMatics