Rebecca Villa

2022-07-09

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.

Expert

If
$f\left(x\right)=\frac{P\left(x\right)}{Q\left(x\right)}$
where $P,Q$ are polynomials, then we have that
$f\left(x\right)Q\left(x\right)=P\left(x\right)$
Now use Leibniz's formula for differentiating a product
$\sum _{r=0}^{n}\left(\genfrac{}{}{0}{}{n}{r}\right){f}^{r}\left(x\right){Q}^{n-r}\left(x\right)={P}^{n}\left(x\right)$
which you can evaluate at $0$ for $n=1,2,\dots$… and you can obtain $\left(n+1{\right)}^{th}$ derivative of $f$ at $0$ from the first n derivatives using the above formula.
The coefficient you need would be $\frac{{f}^{n}\left(0\right)}{n!}$.

Do you have a similar question?