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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Stanley's Enumerative Combinatorics II discusses this issue in Chapter 6, Section 3. $\endgroup$
    – Qiaochu Yuan
    Commented 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$
    – Richard Stanley
    Commented 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
    Commented 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$
    – Max Alekseyev
    Commented Nov 20, 2019 at 21:22

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .