Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
add comment

2 Answers

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.