# How many ways can you make change for a dollar?

This is a generic generating functions problem, and you are left with 1/(x-1)(x^5-1)....(x^50-1) however now I want to find the coefficient of the x^100 term of this expression... how can I do this or do I have to use partial fractions which will take ages...

• I guess you'd have to use complex numbers... but this will take forever... – grigori Nov 23 '16 at 10:08
• I am guessing your "..." may have $1,5,10,25,50$ cent coins, though it rather depends on which dollar you are assuming. – Henry Nov 23 '16 at 10:12
• Multiplying out $(1+x+x^2+\cdots+x^{100})(1+x^5+\cdots+x^{100})\cdots(1+x^{50}+x^{100})$ is not that difficult with a CAS or even a spreadsheet – Henry Nov 23 '16 at 10:14
• yeh that's right, which dollar you are assuming??? – grigori Nov 23 '16 at 10:15
• And yes that's easier than complex numbers ect...just not very elegant – grigori Nov 23 '16 at 10:15

See http://www.maa.org/frank-morgans-math-chat-293-ways-to-make-change-for-a-dollar. This site shows how the answer is obtained with just some intelligent counting. Despite the title of the site Frank Morgan suggests $292$ ways, not counting a dollar coin.