Making Change for a Dollar (and other number partitioning problems) I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem.  I ran across a site that said I could use a generating function similar to the one quoted below:

The answer to our problem ($293$) is the
coefficient of $x^{100}$ in the reciprocal
of the following:
$(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})(1-x^{100})$

But I must be missing something, as I can't figure out how they get from that to $293$. Any help on this would be appreciated.

You should be able to compute it using a Partial Fraction representation (involving complex numbers). For instance see this previous answer: Minimum multi-subset sum to a target
Note, this partial fraction expansion needs to be calculated only one time. Once you have that, you can compute the way to make change for an arbitrary amount pretty quickly.
In this case, I doubt they really did that for finding the coefficient of $x^{100}$. It is probably quicker to just multiply out, ignoring the terms which would not contribute to the coefficient of $x^{100}$. Or you could try computing the partial fraction representation of only some of the terms and then multiply out.
Note, if you are multiplying out to find the coefficient of $x^{100}$, it would be easier not to go to the reciprocal, which arises from considering an infinite number of terms.
You just need to multiply out
$$ (\sum_{j=0}^{100} x^j)\ (\sum_{j=0}^{20} x^{5j})\ (\sum_{j=0}^{10} x^{10j})\  (\sum_{j=0}^{4} x^{25j})\ (1 + x^{100})$$
which would amount to enumerating the different ways to make the change (and in fact is the the way we come up with the generating function in the first place).
You could potentially do other things, like computing the $100^{th}$ derivative at $0$, or computing a contour integral of the generating function divided by $x^{100}$, but I doubt they went that route either.
Hope that helps.
