11
$\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.

  • 1
    Suppose that the denomintor is of degree k, then the first k coefficients can be computed directly from the Taylor series of the generating function and used as initial conditions.2010-09-13
  • 0
    You mean - compute the first k derivatives of the function and apply the Taylor series formula? It sounds reasonable enough, although I wonder if there is a simpler solution (not involving differentiation).2010-09-13
  • 2
    Do you want to reverse the process illustrated by this example? If the recurrence is $a_{n}=5a_{n-1}-6a_{n-2}$, $a_{0}=0,a_{1}=1$, then the generating function $A(x)=\sum_{n=0}^{\infty }a_{n}x^{n}$ can be expanded as $A(x)=5x\underset{A(x)}{\underbrace{\sum_{n=1}^{\infty }a_{n}x^{n}}}-6x^{2}\underset{A(x)}{\underbrace{\sum_{n=0}^{\infty }a_{n}x^{n}}.}$ Hence, $A(x)=P(x)/Q(x)=x/(1-5x+6x^{2})$.2010-09-13
  • 1
    Gadi. Formally one can compute the coefficients as closed loop integrals according to the residue theorem: $a_n = \frac{1}{2 \pi i}\oint z^{-n-1} A(z) dz$, but the actual residue computation would require differentiation also.2010-09-13
  • 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

10

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.

7

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.