1
$\begingroup$

Given a generating function $A(x)$, are there any general techniques for finding the asymptotics of the associated sequence? For example, given the generating function satisfying $A(x) = 1 + x\cdot A\left(\frac{x}{A(-x)}\right)$, is there anything we can say about how fast the coefficients grow?

$\endgroup$
4
  • $\begingroup$ In your example, you are not "given" a generating function, you are given a functional equation for a generating function. Not at all the same thing. $\endgroup$ Aug 3, 2017 at 2:25
  • 2
    $\begingroup$ BTW, your sequence is OEIS sequence A211768. If you do find asymptotics for it, please contribute that to the OEIS. $\endgroup$ Aug 3, 2017 at 2:32
  • $\begingroup$ You are correct, I meant a generating function satisfying a specific equation such as the one above and will change the question accordingly. Given this change in the nature of the question, is there anything that can be deduced about the asymptotics of the sequence from such a functional equation? $\endgroup$
    – Andrew
    Aug 3, 2017 at 2:53
  • $\begingroup$ The OEIS sequence is actually why I am interested in this question, since this generating function is the only way the terms of the sequence are specified $\endgroup$
    – Andrew
    Aug 3, 2017 at 2:55

1 Answer 1

3
$\begingroup$

I don't really understand the significance of your example, but the univariate version of the question is covered very thoroughly in Flajolet-Sedgewick's Analytic Combinatorics, while the (much harder) multivariate version is covered in "Analytic Combinatorics in Several Variable", by Robin Pemantle and Mark Wilson.

$\endgroup$
6
  • $\begingroup$ Thanks for the resource! I asked about this example because the associated sequence for the generating function satisfying the equation came up in my research, and I am interested in its asymptotics $\endgroup$
    – Andrew
    Aug 3, 2017 at 2:55
  • $\begingroup$ Can somebody explain first, what do you call a multivariate version, second, exact reference in Flajolet's book (and also ACSV if possible), because the combinatorial meaning is not straightforward. What does this sequence count? $\endgroup$ Aug 3, 2017 at 20:33
  • $\begingroup$ @SergeyDovgal The books don't address the specific GF (as I had said in my answer), but asymptotics of coefficients of generating functions in general. The generating functions do not actually have to count any combinatorial object... $\endgroup$
    – Igor Rivin
    Aug 3, 2017 at 22:17
  • $\begingroup$ Ah, I see, literally the question asks for "general techniques". I understood this as "general techniques for having asymptotics of g.f. which involves substitutions into itself", not in a broader sense, because I work with generating functions and have never seen such kinds of equations in practice. However, the question still remains, Andrew says that "the equation came up in my research", I wonder what could be the motivation behind the equation. I think that the question really needs a clarification of that type. $\endgroup$ Aug 4, 2017 at 22:52
  • $\begingroup$ I also thought that you were speaking of a multivariate version of the equation presented by Andrew. Sorry for misunderstanding. $\endgroup$ Aug 4, 2017 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.