\problemdata                                                             
        {Generating Functions} % latex-friendly label for the prob.
        {Generating Functions} % The topic(s) of the problem content.  
        {Knuth, Concrete Mathematics, Chapter 7.} % Source (if known)                                          
        {S01 Tutorial 9, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
We will use generating functions to determine how many ways there are to use
pennies, nickels, dimes, quarters, and half-dollars to give $n$ cents change.

\begin{problemparts}
\problempart Write the sequence $P_n$ for the number of ways to use only pennies to
change $n$ cents.  Write the generating function for that sequence.

\solution{
Since there is only one way to change any given amount with only pennies the 
sequence is $P_n = <1, 1, 1, 1, \ldots>$.  The generating function for the 
sequence is $P = 1 + x + x^2 + x^3 + \ldots = \frac{1}{1-x}$.
}

\problempart Write the sequence $N_n$ for the number of ways to use only nickels to
change $n$ cents.  Write the generating function for that sequence.

\solution{
There is no way to change amounts that are not multiples of five with only
nickels.  There is exactly one way to change amounts that are multiples of five
with only nickels.  So the  sequence is $N_n = <1, 0, 0, 0, 0, 1, 0, 0, 0, 0,
1, \ldots>$.  The generating function for the  
sequence is $N = 1 + x^5 + x^{10} + x^{15} + \ldots = \frac{1}{1-x^5}$.
}

\problempart Write the generating function for the number of ways to use only nickels
and pennies to change $n$ cents.  

\solution{
Since P and N are ordinary generating functions for the number of ways to
choose items from disjoint sets, we can apply Rule 5.1 from Lecture 16 and
simply multiply the two generating functions from the previous parts to find a
generating function for the number of way to choose objects from the union of
the sets.  $N \cdot P = \frac{1}{(1-x)(1-x^5)}$. 
}

\problempart Write the generating function for the number of ways to use
pennies, nickels, dimes, quarters, and half-dollars to give $n$ cents change.

\solution{
Generalizing our method gives;
$C = \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})}$.
}

\problempart How do you use this function to find out how many ways are there to
change 50 cents? 

\solution{
The answer is the coefficient to $x^50$ of the $C$ polynomial.
(It happens to be 50.)
}


\end{problemparts}
\end{problem}
                                 