Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
Stanley's Enumerative Combinatorics II discusses this issue in Chapter 6, Section 3. –  Qiaochu Yuan Sep 19 '10 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 '10 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 '10 at 5:34
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.