I have the following generating function, $$G(x,y)=\sum_{n,k \geq 0}a(n,k)x^ny^k = \frac{(y^2-y)x+1}{(y-y^3)x^2-(y+1)x+1}$$ and I am interested in obtaining an asymptotic for the sequence $a(n,k)$ i.e. some nice (relatively) closed form $f(n,k)$ s.t. $$\frac{a(n,k)}{f(n,k)} \rightarrow 1$$ as $(n,k) \rightarrow \infty$. From what I've been able to gather the leading person on this type of analysis in Robin Pemantle, so I have been trying to follow one of his survey papers (https://www.math.upenn.edu/~pemantle/papers/twenty.pdf) in order to compute this. All of the theorems presented in this paper, however, seem to make heavy use of algebraic geometry which I am not very familiar with, so I have been struggling to figure out exactly what I need to compute and how. If someone more familiar with the subject could give me a run down of the necessary computations and how they fit in with the theorems given by Pemantle, that'd be great. One small thing I forgot to mention: for my particular sequence, we can assume that we are in what Pemantle calls the combinatorial case i.e. a priori we know $a(n,k) \geq 0$. Thanks.
1 Answer
I was able to figure out a partial answer and few people have upvoted this so I will go ahead and give it, and maybe someone will respond with a full answer. The answer I was able to obtain is for the center of the sequence i.e. an asymptotic for $a(n,n)$. I essentially just follow Section 8.2 of Pemantle's paper a link for which is given in the question. So we write $$G(x,y)=\frac{F(x,y)}{H(x,y)}=\frac{(y^2-y)x+1}{(y-y^3)x^2-(y+1)x+1}$$ First we need to verify that the variety $V=\{H(x,y)=0\}$ is smooth. This is simply done by making sure that the equations $H(x,y)=0$, $\nabla H(x,y)=0$ do not have simultaneous solutions. This computation can be done using Gröbner basis, mainly the Mathematica command (Pemantle likes using Maple for whatever reason) $$GroebnerBasis[\{H, D[H, x], D[H, y]\}, \{x, y\}]$$ should yield a basis for the trivial ideal. Now we need to find the set of contributing critical points which Proposition 3.11 tells is given by the solutions to the equations $H(x,y)=0$, $xH_x-yH_y=0$. This again can be computed using Gröbner basis, so the Mathematica command $$GroebnerBasis[\{H, x*D[H, x] - y*D[H, y]\}, \{x, y\}]$$ gives $\{-2 + y + y^3, -1 + 2 x\}$. The roots of the first polynomial are $y=1,\frac{1}{2}(-1+i\sqrt{7}),{2}(-1-i\sqrt{7})$ and the second $x=\frac{1}{2}$, so there is only one positive, real, simultaneous solution and thus the set of contributing critical points is the singleton $\{(\frac{1}{2},1)\}$. Now we simply plug-in to the formula given by Corollary 3.21 to obatin $$a(n,n) \sim \frac{2^n}{\sqrt{\pi n}}$$
-
$\begingroup$ It seems you have worked out how to do it. Three notes: (1) Robin Pemantle is only one of the authors - guess who the other is. (2) We have a book published in 2013 that may be easier to follow. (3) There is a package incorporated into Sage that does many of these computations automatically. $\endgroup$ Oct 1, 2016 at 20:57