How to extract the diagonal from a bivariate generating function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T07:57:11Z http://mathoverflow.net/feeds/question/39287 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39287/how-to-extract-the-diagonal-from-a-bivariate-generating-function How to extract the diagonal from a bivariate generating function Thomas Li 2010-09-19T09:05:30Z 2012-10-10T22:39:50Z <p>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$.</p> <p>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)$?</p> <p>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.</p> <p>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)}$.</p> http://mathoverflow.net/questions/39287/how-to-extract-the-diagonal-from-a-bivariate-generating-function/109338#109338 Answer by Mark C. Wilson for How to extract the diagonal from a bivariate generating function Mark C. Wilson 2012-10-10T22:39:50Z 2012-10-10T22:39:50Z <p>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.</p> <p>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".</p> <p>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.</p>