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..

  • 0
    I described a method that satisfies me in that earlier question.2012-08-03

0 Answers 0