logic/sequences

[Tonya Krasienko]

How do I solve this problem? I suspect that I should be able to name a sequence and solve it that way, but I cannot figure it out. I worked a very long time trying to figure it out the slow-head way and came up with an answer of 49. I don't know if 49 is wrong or right, but I really would like to know the efficient way of solving it. Thanks.
How many different ways can you make change for a $100 bill using $5, $10,
$20, and $50 bills?

 

[pka]

The really good news is that you are absolutely right!
49 is the correct answer!

Now the bad news: to do the problem correctly you will need an advanced calculator or a computer algebra system. We need to expand
\(\displaystyle \L
\left( {\sum\limits_{k = 0}^{20} {x^{5k} } } \right)\left( {\sum\limits_{k = 0}^{10} {x^{10k} } } \right)\left( {\sum\limits_{k = 0}^5 {x^{20k} } } \right)\left( {\sum\limits_{k = 0}^2 {x^{50k} } } \right)\).

In that expansion the coefficient of x<SUP>100</SUP> is 49. That is the answer to your question.