Finding the power series of a rational functionIn 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.

Question

Finding the power series of a rational functionIn 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&#039;s really just the question of finding the finite initial values.

Wade Atkinson · Accepted Answer

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&#039;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      !      .