How to extract the diagonal from a bivariate generating function

2010-09-19T09:05:30Z

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)}$.

Answer by Mark C. Wilson for How to extract the diagonal from a bivariate generating function

2012-10-10T22:39:50Z

The paper "A new method for computing asymptotics of diagonal coefficients of multivariate generating functions" by A. Raichev and M.C. Wilson (DMTCS 2007, arXiv, author homepages) explains more about this topic.

In particular, if you really want asymptotics, the explicit computation of the diagonal GF is unnecessary in most cases. There will be more on this topic in the forthcoming book by Pemantle and Wilson, "Analytic Combinatorics in Several Variables".

In the case of a 2-variable algebraic GF, I would see whether it arises naturally as a diagonal of a higher degree rational GF and start from there using methods as in the last paragraph.

How to extract the diagonal from a bivariate generating function - MathOverflow

How to extract the diagonal from a bivariate generating function

Answer by Mark C. Wilson for How to extract the diagonal from a bivariate generating function