1
$\begingroup$

Many combinatorial problems can be solved using generating functions.

In such a case, we obtain a function $f(x)$, which (for usual) has a taylor-expansion: $$ f(x) = \sum_{n\ge 0 } a_n x^n $$ So that the coefficients $a_n$ are exactly the elements of the sequence we're looking for.

Further, we may assume that the function $f(x)$ is given in closed form, i.e. as a finite function built using only elementary functions.

Now, unlike when we want to determine the Taylor-expansion, we now want a single coefficient $a_k$, for some fixed $k$.

What's the most efficient method to do this?

$\endgroup$
3
  • $\begingroup$ That’s pretty broad, because your function can be defined in a variety of ways: functional equation, implicit expression of $f(x)$, infinite product, and so on. $\endgroup$
    – Aphelli
    Aug 4, 2019 at 8:05
  • $\begingroup$ @Mindlack True. Though I'd be interested for the complexity of each of those cases, I've followed your advise and restricted the question to functions in closed form $\endgroup$
    – Sudix
    Aug 4, 2019 at 19:40
  • $\begingroup$ Now posted to MO, mathoverflow.net/questions/338244/… $\endgroup$
    – Gerry Myerson
    Aug 13, 2019 at 13:15

1 Answer 1

Reset to default
1
$\begingroup$

An efficient method implemented by some computer algebra systems uses polynomial Newton-Raphson division and term by term integration to compute logarithms of series expansions and uses the inverse of this process implemented by another Newton Raphson process to compute exponentials of series expansions. The number of steps needed to compute the nth term of an elementary function of a given series expansion is then proportional to a power of $\log_2(n)$.

$\endgroup$
1
  • $\begingroup$ Can you tell me the name of this method? I don't see at all how this is supposed to work out in $O(log_2(n))$ $\endgroup$
    – Sudix
    Aug 5, 2019 at 16:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .