11
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Stanley's Enumerative Combinatorics II discusses this issue in Chapter 6, Section 3. $\endgroup$ Sep 19, 2010 at 17:21
  • 2
    $\begingroup$ 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)$. $\endgroup$ Sep 20, 2010 at 1:45
  • $\begingroup$ @Richard, thanks for the reference. I found that the diagonal of a algebraic bivariate generating function is not necessarily algebraic. $\endgroup$
    – Thomas Li
    Sep 28, 2010 at 5:34
  • $\begingroup$ 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$. $\endgroup$ Nov 20, 2019 at 21:22

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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