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).
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.
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 |
163 163 |
Hence, there are 163 ways to make change for 89 cents.