Reference request - Theory of rational multivariate generating functions (extracting coefficients of their taylor expansion)

Question

I'm looking for a book/text/paper/etc. that develops the theory of multivariate (/bivariate) generating functions with special focus on how to extract coefficients.

If possible, I'd like the source to develop a theorem that allows one to directly transform the rational generating function into the underlying coefficient-sequence.

In the case of univariate generating functions this theory looks roughly like this:
Given a rational generating function $F(x)= \frac{P(x)}{Q(x)}$ of $ \sum_{n\ge 0}a_n x^n$ determine the reciprocals of the zeroes of $Q(x)$ with their multiplicity.

This then gives us the function class of $a_n$. We substitute in the first few values and solve the equation system for the unknowns, and arrive at a formula for $a_n$.

Can anybody hint me to good references for this theory?

Answer 1

It sounds like you'd be interested in the text Asymptotic Combinatorics in Several Variables by Robin Pemantle and Mark Wilson, as well as their article Twenty Combinatorial Examples of Asymptotics Derived from Multivariable Generating Functions.

Answer 2

After some more researching, it turns out that it's doubtful that such a theory exists, at least not in a calculus using only elementary functions:

Even rather simple bivariate generating functions like
$$F(x,y) = \frac{x·(x - 2)}{(x - 1)^2·(x + y - 2)}$$ seem to develop into taylor-series with coefficients that have no closed formula.

(The upper generating function develops into the taylor-series:

$$ \sum_{n,k\ge 0} \frac{\displaystyle\sum_{i=0}^n(i + 2)·\binom{n - i + k}{ n - i}\cdot \frac 1{2^{n - i + k - 3}}}{16} x ^{n+1} y^k $$ The coefficients have a known closed form involving the hypergeometric sum, but none only using elementary functions (at least as far as I could deduce)

There are however instances that admit closed formulas for the coefficients of the taylor-series, with many special cases coming from lattice-theory.

While not necessarily achieving a closed formula, a method that at least always allows one to develop a rational generating function into a taylor-series is the following:

Let $ F(x_1,..,x_n) = P(x_1,..,x_n)/Q(x_1,..,x_n) := P/Q$.

• Factorize Q into factors $Q_1\dots Q_k$ so that for each factor $Q_i$ you can develop the taylor-series of $1/Q_i$ (at worst you'll have to split $Q$ into is linear factors, which all admit a simple taylor-series)..

• We now have $F = 1/Q_1 \cdots 1/Q_k$. We then develop each factor into its taylor-series.

• Finally, we convolute the taylor-series and try to simplify the resulting expression.

Even for multivariate generating functions however there are special classes that always admit a closed formula.
One for example is when a rational generating function $F(x_1,..,x_n)$ is seperable into $F(x_1,..,x_n) = F_1(x_1) \cdots F_n(x_n)$.

In this case the denominator of $F(x_1,..,x_n)$ admits a factorization of linear factors which each have only a single variable. We can then group all linear factors which the same variable together, and apply the method from above, which in this case always gives a closed formula.

Answer 3

There's some relevant material in Chapter 6 of Stanley's Enumerative Combinatorics, Volume 2 (particularly, extracting the diagonal $\sum f(n, n) x^n$ of a bivariate rational generating function $\sum f(n, m) x^n y^m$), and some more in Chapter IX of Flajolet and Sedgewick's Analytic Combinatorics (which is mostly about getting asymptotics).

Answer 4

The problem: "given a rational function $f \in Q(x_1,\ldots,x_n)$ and a monomial $M$, find the coefficient of $M$ in $f$" is NP-hard. That implies that probably you can't go further than some occasionally successful heuristics.