Finding the power series of a rational function In many combinatorial enumeration problems it is po

Rebecca Villa

Rebecca Villa

Answered question

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.

Answer & Explanation

Wade Atkinson

Wade Atkinson

Beginner2022-07-10Added 12 answers

If
f ( x ) = 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
r = 0 n ( n r ) f r ( x ) Q n r ( x ) = P n ( x )
which you can evaluate at 0 for n = 1 , 2 , … and you can obtain ( n + 1 ) t h derivative of f at 0 from the first n derivatives using the above formula.
The coefficient you need would be f n ( 0 ) n ! .

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?