# How to extract the diagonal from a bivariate generating function

Let $F(s,t)= \sum_{i,j} f(i,j) s^i t^j$, which is a bivariate generating funcion of the number $f(i,j)$ for some enumeration problem. Sometimes we know about $F(s,t)$, but what we really need is the number $f(i,i)$ with the generating function $G(x)= \sum_i f(i,i) x^i$, called the diagonal of $F$.

The question is how to obtain the diagonal $G(x)$ from $F(s,t)$? Furthermore, how to get the asymtotic formula for $f(i,i)$ from $F(s,t)$?

One way to do this is shown as follows: $G(x)$ is the constant term of $F(s,\frac{x}{s})$ regarded as a Laurent series in $s$ whose coefficients are power series in x. And we can use Cauchy's integral theorem and Residue Theorem to compute.

This method works when $F(s,t)$ is rational. But when $F(s,t)$ is more complicated, it seems not workable. An example is $F(s,t)=\frac{4 s t}{\sqrt{1-4 s^2}\sqrt{1-4 t^2}(\sqrt{1-4 s^2}\sqrt{1-4 t^2}-4 s t)}$.

• Stanley's Enumerative Combinatorics II discusses this issue in Chapter 6, Section 3. Sep 19, 2010 at 17:21
• An authority on the asymptotics of $f(i,j)$ for rational $F(s,t)$ is Robin Pemantle. See math.upenn.edu/~pemantle/papers/Papers.html. I don't know what to do in general about nonrational $F(s,t)$. Sep 20, 2010 at 1:45
• @Richard, thanks for the reference. I found that the diagonal of a algebraic bivariate generating function is not necessarily algebraic. Sep 28, 2010 at 5:34
• An important example is given by $F(s,t)$ of the form $\frac{\phi(s)}{1+t\psi(s)}$, where the diagonal can be obtained with Lagrange-Buermann formula. This case can be recognized by equality $\left(\frac{\partial}{\partial t}\right)^2 \frac1{F(s,t)} = 0$. Nov 20, 2019 at 21:22