Archive for the 'analysis' Category

Extracting the diagonal

October 7, 2009

Needless to say, I have been very, very busy. But enough about me.

Suppose you are given a bivariate generating function

\displaystyle F(x, y) = \sum_{m, n \ge 0} f(m, n) x^m y^n

in “closed form,” where I’ll be vague about what that means. Such a generating function may arise, for example, from counting lattice paths in \mathbb{Z}_{\ge 0}^2; then f(m, n) might count the number of paths from (0, 0) to (m, n). If the path is only constrained by the fact that its steps must come from some set S \subset \mathbb{Z}_{\ge 0}^2 of steps containing only up or left steps, then we have the simple identity

\displaystyle F_S(x, y) = \frac{1}{1 - \sum_{(a, b) \in S} x^a y^b}.

Question: When can we determine the generating function \displaystyle D_F(x) = \sum_{n \ge 0} f(n, n) x^n in closed form?

I’d like to discuss an analytic approach to this question that gives concrete answers in at least a few important special cases, including the generating function for the central binomial coefficients, which is our motivating example.

Read the rest of this entry »

Posted in algebraic combinatorics, analysis | 7 Comments »
Tags: , , , ,