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?
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$– Robert IsraelCommented 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$– Robert IsraelCommented 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$– AndrewCommented 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$– AndrewCommented Aug 3, 2017 at 2:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.
answered Aug 3, 2017 at 1:24
-
$\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$– AndrewCommented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Aug 4, 2017 at 22:58