Finding the power series of a rational function

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.