Finding the power series of a rational function In many combinatorial enumeration problems it is possible to find a rational generating function (i.e. the quotient of two polynomials) for the sequence in question. The question is - given the generating function, how can we find (algorithmically) the values of the sequence, i.e. the coefficients of the corresponding power series?
I know that for a rational generating function, the sequence satisfies a recurrence relation given by the coefficients of the polynomial in the denominator, so it's really just the question of finding the finite initial values.
 A: If one is computing by hand then the following small observation is useful: If $f(x) = P(x)/Q(x)$ and $Q(x) = x^d(1 - g(x))$ for some $d \geq 0$ and some polynomial $g(x)$ (which we may assume after rescaling
$P(x)$ and $Q(x)$), then using the formula for a geometric series we find that
$$f(x) = x^{-d}P(x)(1 + g(x) + g(x)^2 + \cdots ).$$
For explicit pen and paper computations, I normally find this is the simplest way to
compute the Taylor series for $f(x)$.
A: Sometimes partial fractions decomposition is useful. Especially if there are only simple poles, since then each partial fraction can be expanded in a geometric series.
A: If $$f(x) = \frac{P(x)}{Q(x)}$$ where $P,Q$ are polynomials, then we have that
$$f(x)Q(x) = P(x)$$
Now use Leibniz's formula for differentiating a product
$$\sum_{r=0}^{n} {n \choose r} f^{r}(x) Q^{n-r}(x) = P^{n}(x)$$
which you can evaluate at $0$ for $n=1,2,\dots$ and you can obtain $(n+1)^{th}$ derivative of $f$ at $0$ from the first $n$ derivatives using the above formula.
The coefficient you need would be $\frac{f^{n}(0)}{n!}$.
This should be easily doable by a computer. No integration etc needed.
