# generating functions for pennies and nickels

We will use generating functions to determine how many ways there are to use pennies and nickels to give n cents change.

(i) Write the sequence Pn for the number of ways to use only pennies to change n cents. Write the generating function for that sequence.

(ii) Write the sequence Nn for the number of ways to use only nickels to change n cents. Write the generating function for that sequence.

(iii) Write the generating function for the number of ways to use pennies and nickels to change n cents.

(iv) Write the generating function for the number of ways to use pennies, nickels and dimes to change n cents.

the only thing i can think of so far is that pennies will have <1,1,1,1,1,...> 1+x+x^2+x^3+... and nickels will have <1,0,0,0,1,0,0,0,1,....> or something like that... don't know how to do the rest

-

For pennies you have the sequence $\langle 1,1,1,\dots\rangle$, which as you say correponds to the formal power series

$$1+x+x^2+\ldots=\sum_{n\ge 0}x^n\;.$$

That’s just a geometric series, so you know what the generating function is (even if you didn’t realize it right away:

$$\sum_{n\ge 0}x^n=\frac1{1-x}\;.$$

For nickels you can do almost the same thing. Your sequence is $\langle 1,0,0,0,0,1,0,\dots\rangle$, corresponding to another geometric series:

$$1+x^5+x^{10}+\ldots=\sum_{n\ge 0}x^{5n}=\sum_{n\ge 0}\left(x^5\right)^n=\frac1{1-x^5}\;.$$

For pennies and nickels you want

$$\left(1+x+x^2+\ldots\right)\left(1+x^5+x^{10}+\ldots\right)\;:\tag{1}$$

$(1)$ has one $x^n$ term for every way to write $n$ in the form $5m+k$ with $m,k\in\Bbb N$, which is precisely the number of ways to make the amount $n$ with nickels and pennies. Clearly, then, the generating function is just

$$\frac1{(1-x)(1-x^5)}\;.$$

I’ll leave the last part to you.

-
I like your last paragraph, +1 –  Rustyn Jan 31 '13 at 5:25
great explanation.. thanks so the last part i suppose will be 1/((1-x)(1-x^5)(1-x^10)) by the same principle we used pennies and nickels to change n cents. –  dotdotdot Jan 31 '13 at 5:32
@dotdotdot there is a great PDF listed in the comments about this topic, just FYI in case you're interested. –  Rustyn Jan 31 '13 at 5:36
@dotdotdot: You’re welcome. Yes, that’s exactly right. –  Brian M. Scott Jan 31 '13 at 5:37

For $3$: Consider multiplies of $5$:

The coefficients go like: $<1,1,1,1,2,2,2,2,2,3,3,3,3,3,...>$,

(We obtain a way to give back change at each multiple of $5$).

Each coefficient is obtained by multiplying the two previous power series:

$$(1 + x + x^2 + ...)(1 + x^5 + x^{10}+...)$$ See Brian's answer for a simplification of this function.

-