Coin Problem

Coin Problem

How many ways are there to make change for n cents using only pennies (1 cent), nickels (5 cents), dimes (10 cents), and quarters (25 cents)?

Let a_n denote the number of ways. Then the generating function for A(x)=\sum_{n\ge0} a_n x^n is given by A(x)=\left(\frac{1}{1-x}\right) \left(\frac{1}{1-x^5}\right) \left(\frac{1}{1-x^{10}}\right) \left(\frac{1}{1-x^{25}}\right).

x=var('x')
A=1/( (1-x) * (1-x^5) * (1-x^10) * (1-x^25) )
print A 
       
1/((x - 1)*(x^5 - 1)*(x^10 - 1)*(x^25 - 1))
1/((x - 1)*(x^5 - 1)*(x^10 - 1)*(x^25 - 1))

To find the value of a_n for a particular n, we use Taylor's Theorem to expand the generating function as a power series about x=0 and then extract the appropriate coefficient.

taylor(A,x,0,10) 
       
4*x^10 + 2*x^9 + 2*x^8 + 2*x^7 + 2*x^6 + 2*x^5 + x^4 + x^3 + x^2 + x
+ 1
4*x^10 + 2*x^9 + 2*x^8 + 2*x^7 + 2*x^6 + 2*x^5 + x^4 + x^3 + x^2 + x + 1
taylor(A,x,0,90).coeff(x,89) 
       
163
163

Hence, there are 163 ways to make change for 89 cents.