How many ways to pay

Question

Let $a_n$ be the number of ways in which you can pay $n$ amount with coins valued at 1, 2, 5, 10, 20, 50. Find the generating function for $(a_0,a_1,a_2,…)$. And find the value of $a_{23}$. Find the generating function where you can use at most 10 coins valued at 1, 7 coins valued at 2 and 6 coins valued at 5.

What I have so far is $f(x) = \frac1{1-x}\frac1{1-x^2}\frac1{1-x^5}\frac1{1-x^{10}}\frac1{1-x^{20}}\frac1{1-x^{50}}$

How would I proceed with finding the answer for $a_{23}$?

Answer 1

You have found the generating function. Cool. The reason we use generating functions is because they're shorthand for certain series, and the way multiplication of those series work closely mimics the way the combinatorics of your coin problem works.

So, in order to use the generating functions to actually find an answer, the most straight-forward way is to go back to those series, and find the coefficient of the $x^{23}$ term: $$ f(x) = (1+x+x^2 + \cdots)\cdot (1 + x^2 + x^4 + \cdots)\cdot(1 + x^5 + x^{10} + \cdots)\\ {}\cdot(1 + x^{10} + x^{20} + \cdots)\cdot(1 + x^{20} + x^{40} + \cdots)\cdot(1 + x^{50} + x^{100} + \cdots) $$ We see immedaitely that any term of higher degree than $23$ may be safely discarded without changing our result: $$ f(x)\approx(1 + x + x^2 + \cdots + x^{23})\cdot(1 + x^2 + x^4 + \cdots + x^{22})\\ {}\cdot(1 + x^5 + x^{10} + x^{15} + x^{20})\cdot(1 + x^{10} + x^{20})\cdot(1 + x^{20}) $$ And then we get to multiplying (still discarding any terms higher than $x^{23}$ as we go): $$ \approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + \cdots + 12x^{22} + 12x^{23})\\ \cdot(1 + x^5 + x^{10} + x^{15} + x^{20})\cdot(1 + x^{10} + x^{20})\cdot(1 + x^{20})\\ \approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + \cdots + 12x^{22} + 12x^{23})\\ \cdot(1 + x^5 + x^{10} + x^{15} + x^{20})\cdot(1 + x^{10} + 2x^{20})\\ \approx (1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + \cdots + 12x^{22} + 12x^{23})\\ \cdot(1 + x^5 + 2x^{10} + 2x^{15} + 4x^{20}) $$ And now that we only have two brackets we can forget everything else, and look directly at the terms whose degrees add up to $23$. We get: $$ 12x^{23}\cdot 1 + 10x^{18}\cdot x^5 + 7x^{13}\cdot 2x^{10} + 5x^8\cdot 2x^{15} + 2x^3\cdot 4x^{20}\\ = 54x^{23} $$ So there are 54 ways to make $23$ with the given coins.

With the given limitation, instead of the infinite series we get finite series (polynomials) for the limited coins. So instead of $(1 + x + x^2 + \cdots)$, we use $(1 + x + x^2 + \cdots + x^{10})$, or its more succinct representative $\frac{1-x^{11}}{1-x}$. Similarily, the two-coin terms changes to $\frac{1 - x^{16}}{1-x^2}$ and the five-coin term to $\frac{1-x^{35}}{1-x^5}$. So we get the generating function $$ g(x) = \frac{1-x^{11}}{1-x}\cdot\frac{1 - x^{16}}{1-x^2}\cdot\frac{1-x^{35}}{1-x^5}\cdot\frac{1}{1-x^{10}}\cdot\frac{1}{1-x^{20}}\cdot\frac{1}{1-x^{50}} $$

Answer 2

Let $b_n$ be the number of ways to make change from $[1,2]$. Fill out the table $b_1,b_2,\dots,b_{23}$ by brute force.

Let $c_n$ be the number of ways to make change from $[1,2,5]$. Note that $$ c_n=c_{n-5}+b_n, $$ so use that recursion, plus the filled out $b$ table, to fill out $c_1,c_2,\dots,c_{23}$.

Then, let $d_n$ be the number of ways to make change from $[1,2,5,10]$, and use the $c$ table and a similar recursion to fill out the $d$ table, then let $e_n$ the number of ways to make change from $[1,2,5,10,20]$ and do the same. You want $e_{23}$.