2
$\begingroup$

We consider the asymptotics of the coefficients of generating function $y(x)$, which is defined by the implicit function $y= F(x,y)$.

Let $F(x,y)$ be a rational function in $x$ and $y$, such that $F(x,y)$ has non-negative coefficients of development in $x$ and $y$. Further $F(x,y)$ is not a linear function of $y$. Can we conculde that $[x^n]y(x)\sim \rho^{-n} n^{-\frac{3}{2}}$?

If not, what kind of additional condition do we need to prove such asymptotics?

It seems that it can be derived from singularity analysis. One reference could be Flajolet and Sedgewick's Book "Analytic Combinatorics". However the proof in there is rather obscure to me.

I think that we still need to additional condition to make that conclusion, such as there exist $r>0$ and $s>0$ satisfying \begin{equation} F(r,s)=s, F_x(r,s)=1. \end{equation}

Any reference about this topic would be appreciated. Thank you in advance.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You say F is rational in y, but did not say anything about dependence of F on x, so how can you expect any asymptotic? $\endgroup$
    – Alexandre Eremenko
    Commented Sep 15, 2012 at 14:21
  • $\begingroup$ @Alexandre Eremenko Thanks. Corrected. $\endgroup$
    – Thomas Li
    Commented Sep 15, 2012 at 16:43
  • $\begingroup$ Where is the proof in Flajolet-Sedgewick? $\endgroup$
    – Igor Rivin
    Commented Sep 16, 2012 at 0:07
  • $\begingroup$ @Igor Rivin In the proof of Theorem VII.6 (DLW theorem) on page 490 (eletronic version) they claim that it is true for polynomial F(x,y). $\endgroup$
    – Thomas Li
    Commented Sep 16, 2012 at 7:52

1 Answer 1

Reset to default
1
$\begingroup$

A set of conditions which imply this asymptotic is given by Theorem VII.6, which you mention in your remark. These additional condition is that the equation is "a-proper". The theorem is not true without this additional condition.

Improve this answer
$\endgroup$

You must log in to answer this question.

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