Background:
I'd like to solve the Counting change problem by generating function.
The problem is described here:
How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?
There are many possible ways, e.g. tree recursion, dynamic programming, SMT solver, etc.
My attempt is to use a generating function:
This problem can be modeled as counting the number of nonnegative integral solutions of the equation:
$\displaystyle{ e_1 + 5e_2 + 10e_3 + 25e_4 + 50e_5 = n}$
Thus the generating function is:
$\displaystyle{ g(x) = \frac{1}{1-x} \frac{1}{1-x^5} \frac{1}{1-x^{10}} \frac{1}{1-x^{25}} \frac{1}{1-x^{50}}}$
but how to find the general formula $h(n)$ for $g(x)$? i.e.
$g(x) = \sum_{n=0}^\infty h(n) x^n $
AFAIK, the traditional method is to use partial fractions, i.e.
$ \displaystyle{\frac{1}{1-x} \frac{1}{1-x^5} \frac{1}{1-x^{10}} \frac{1}{1-x^{25}} \frac{1}{1-x^{50}} = \frac{c_1}{1-x} + \frac{c_2}{1-x^5} + \frac{c_3}{1-x^{10}} + \frac{c_4}{1-x^{25}} + \frac{c_5}{1-x^{50}}} $
then simplify it and solve $c_1$, $c_2$, $c_3$, $c_4$, $c_5$.
However, for this example it seems very difficult ... (or better method?)
My question is that
Is there any mathematical tool that can find the general formula of the generating function directly? I have tried the generating function in wolfrmalpha, it cannot get the general formula (although it can get Taylor series).
Thanks.
P.s. I believe that once we get the general formula, computing the number of ways to change any given amount of money will be very fast.
The partial fraction decomposition can be done theoretically but I wouldn't want to do it. As people have said in the comments, the problem is that there are many multiple roots so it's fairly annoying even to write down the general form let alone to solve for its coefficients, and your general form is not correct. Over $\mathbb{Q}$ the denominator factors as
$$(1 - x)^5 (1 + x)^2 \Phi_5(x)^4 \Phi_{10}(x)^2 \Phi_{25}(x)^2 \Phi_{50}(x)$$
where $\Phi_n(x)$ is the $n^{th}$ cyclotomic polynomial; this follows from the factorization $x^n - 1 = \prod_{d \mid n} \Phi_d(x)$ and it means the general form of the partial fraction decomposition over $\mathbb{Q}$ is
$$\frac{c_1(x)}{(1 - x)^5} + \frac{c_2(x)}{(1 + x)^2} + \frac{c_5(x)}{\Phi_5(x)^4} + \frac{c_{10}(x)}{\Phi_{10}(x)^2} + \frac{c_{25}(x)}{\Phi_{25}(x)^2} + \frac{c_{50}(x)}{\Phi_{50}(x)}$$
where the $c_i$ are all polynomials of degree less than the degree of the denominator. Over $\mathbb{C}$ we'd have a summand for each of the $50^{th}$ roots of unity, many of which have multiplicities, but there's a lot of redundancy in this description because of Galois invariance so I think it's easier to think about the partial fraction decomposition over $\mathbb{Q}$.
If you want to compute the partial fraction decomposition from here you can do it by clearing denominators and then substituting in various roots of unity, although the multiplicities mean you may have to compute various derivatives also which could get messy. It's all theoretically a finite computation though.
It's also worth noting that the largest contributors to the sum will come from the $\frac{1}{(1 - x)^5}$ term (which will contribute a quartic polynomial) and the $\frac{1}{\Phi_5(x)^4}$ term (which will contribute a cubic quasipolynomial with period $5$). The terms with multiplicity $2$ in the denominator only contribute linear quasipolynomials and the final $\Phi_{50}(x)$ term only contributes a constant quasipolynomial (which is to say a periodic function, with period $50$). So if you only want an accurate approximation to the answer the generating function may be able to do that for you more easily than computing the whole thing.
Also it may be possible to simplify the computation by writing the generating function as $\frac{1}{(1 - x) Q(x^5)}$ where $Q(x) = (1 - x)(1 - x^2)(1 - x^5)(1 - x^{10})$ and first computing the partial fraction decomposition of $\frac{1}{Q(x)}$, then substituting in $x^5$ and multiplying by $\frac{1}{1 - x}$.