3
$\begingroup$

Possible Duplicate:
Making Change for a Dollar (and other number partitioning problems)

The problem is:

How many are ways to change one dollar using coins: 5,10,20,50 cents?

The method is completely clear to me. Generating function is: $$\frac{1}{1-x^5}\cdot\frac{1}{1-x^{10}}\cdot\frac{1}{1-x^{20}}\cdot\frac{1}{1-x^{50}}$$ and we are looking for the coefficient before $x^{100}$ in series expansion of this function. But I don't know, how to do it quickly? Of course, I can decompose this function to simple fractions, but it is really brute force approach and it will take a lot of time. Are there any good general methods for finding coefficients before $x^n$ in series expansions of functions? It is often very useful..

  • 1
    [Here](http://www.wolframalpha.com/input/?i=series+for+1%2F%28%281-x^5%29%281-x^10%29%281-x^20%29%281-x^50%29%29+at+x%3D0)'s one method (click on "More Terms" a couple of times).2012-08-03
  • 0
    You mean Taylor expansion? Right, but for big $n$ it fails unless given function has a "pretty" Taylor expansion.2012-08-03
  • 0
    calculate $\frac{1}{100!}\frac {d^{100}}{dx^{100}}\left(\frac{1}{1-x^5}\cdot\frac{1}{1-x^{10}}\cdot\frac{1}{1-x^{20}}\cdot\frac{1}{1-x^{50}}\right)$ and set $x=0$2012-08-03
  • 0
    @J.M. thanks a lot!! Now I see, this method with recursion for each coin is brilliant. This is what I needed.2012-08-03
  • 0
    If you've managed to figure out what to do, you might want to write an answer to your question...2012-08-03
  • 0
    Or rather to the other question, since this one is likely to get closed as a duplicate.2012-08-03
  • 0
    I described a method that satisfies me in that earlier question.2012-08-03

0 Answers 0