12
$\begingroup$

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.

  • 0
    in what sense is differentiation complicated? The formal act of differentiating a rational function is about as simple algorithmically as it gets.2010-09-13

3 Answers 3

11

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.

8

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

4

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.