Changing money and generating functions.

combinatoricsgenerating-functions

How can I prove it?

In $2010$, there are fifty commemorative quarters in general circulation in the U.S., one the each state, and sixteen different presidential dollar coins, showing Washington through Lincoln on the observe. Prove that the number of ways to make $25k$ cents in change using just these $66$ different coins is $$
\sum_{a+b+2c=k}(-1)^{b+c}\begin{pmatrix} 65+a\\ a\end{pmatrix}\begin{pmatrix} 15+b \\ b \end{pmatrix} \begin{pmatrix} 15+c \\ c\end{pmatrix}
$$
Then use this formula to determine the number of ways to change one dollar using just these coins.

$\textbf{My attempt:}$ I'm trying to use the generating function for to solve this problem.

Let us define $a_{k}$ to be the number of ways to make $25k$ cents in the change and let $A(x)$ be a generating function for $a_{k}$: $$A(x)=\sum_{k}a_{k}x^{k}$$

I think I should to use that $$\frac{1}{1-x}=1+x^{2}+x^{3}+\cdots$$ and then I can use Maclaurin series for $A(x)$.

Best Answer

First observe that

$$\sum_{a+b+2c=k}(-1)^{b+c}\binom{65+a}a\binom{15+b}b\binom{15+c}c$$

is the coefficient of $x^k$ in the product

$$\left(\sum_{a\ge 0}\binom{65+a}ax^a\right)\left(\sum_{b\ge 0}(-1)^b\binom{15+b}bx^b\right)\left(\sum_{c\ge 0}(-1)^c\binom{15+c}cx^{2c}\right)\,.$$

In closed form this is the product

$$\begin{align*} \frac1{(1-x)^{66}}\cdot\frac1{(1+x)^{16}}\cdot\frac1{(1+x^2)^{16}}&=\frac1{(1-x)^{66}(1+x)^{16}(1+x^2)^{16}}\\ &=\frac1{(1-x)^{50}(1-x^2)^{16}(1+x^2)^{16}}\\ &=\frac1{(1-x)^{50}(1-x^4)^{16}}\\ &=\frac1{(1-x)^{50}}\cdot\frac1{(1-x^4)^{16}}\,, \end{align*}$$

which in turn is the closed form of

$$\left(\sum_a\binom{49+a}ax^a\right)\left(\sum_b\binom{15+b}bx^{4b}\right)\,.$$

The coefficient of $x^k$ in this product is

$$\sum_{a+4b=k}\binom{49+a}a\binom{15+b}b\,;$$

can you see why this is the number of ways to make change for $25k$ cents using these $66$ types of coins?