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$
  • $\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$ – Robert Israel Aug 3 '17 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$ – Robert Israel Aug 3 '17 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 '17 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 '17 at 2:55
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$
  • $\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 '17 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$ – Sergey Dovgal Aug 3 '17 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 '17 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$ – Sergey Dovgal Aug 4 '17 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$ – Sergey Dovgal Aug 4 '17 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.