MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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. – Qiaochu Yuan 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)$. – Richard Stanley 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. – Thomas Li Sep 28 2010 at 5:34