25 October 2007

Something I didn't know about generating functions (and probably should have)

I learned today, while reading Flajolet and Sedgewick's Introduction to the Analysis of Algorithms, something that I probably should have known but didn't. I should have known this because I've learned what ordinary and exponential generating functions are about four times now (since combinatorics classes often don't assume that much background, they seem to get defined over and over again).

Namely, given a sequence a0, a1, a2, ..., we can form its exponential generating function $A(z) = \sum_{n=0}^\infty a_n {z^n \over n!}$. Then the ordinary generating function $\tilde{A}(z) = \sum_{n=0}^\infty a_n z^n$ is given by the integral
\tilde{A}(z) = \int_0^\infty A(zt) e^{-t} \, dt

when this integral exists. (This is something like the Laplace transform.)

The proof is straightforward, and I'll give it here. (I'll ignore issues of convergence.) Consider that integral; by recalling what A(z) is, it can be rewritten as
\int_0^\infty \left( \sum_{k=0}^\infty {a_k \over k!} (zt)^k \right) e^{-t} \, dt

and we can interchange the integral and the sum to get
\sum_{k=0}^\infty \left( \int_0^\infty {a_k \over k!} (zt)^k e^{-t} \, dt \right)

But we can pull out the part of the integrand which doesn't depend on t to get
\sum_{k=0}^\infty \left( {a_k \over k!} z^k \int_0^\infty t^k e^{-t} \, dt \right)

and that integral is well-known as the integral representation for the gamma function. The integral is k!, which cancels with the k! in the denominator, and we recover $\tilde{A}(z) = \sum_{k=0}^\infty a_k z^k$.

It's easy to come up with examples to verify this; for example, the exponential generating function of the binomial coefficients ${N \choose 2}$ is z2ez/2; plugging this into our formula gives z2(1-z)-3, which is the ordinary generating function of the same sequence.

I'm not sure how useful it is to know this, though... I can't think of too many times where I had an exponential generating function for some sequence and thought "oh, if only I had the ordinary generating function."
Posted by at
Labels: ,

5 comments:

dimpase said...

Combinatorics people never seem to know enough analysis. Indeed, I don't recall this formula mentioned in any standard texts on generatingfunctionology.

Reminds me of a wonderful formula for the asymptotics of Toeplitz determinants (given by a Laurent generating function for 1st row and column - 0th degree term naturally is used for the main diagonal entries) due to Szego (Szego Strong Limit Thm and its later generalisations) that seems nowhere to be found in combinatorics literature, e.g. not in otherwise encyclopedic "Advanced Determinantal Calculus" by Krattenthaler. When I needed such a formula, it took me quite a bit of googling and mathscinetting...

October 25, 2007 at 7:44 PM
Suresh Venkatasubramanian said...

Btw, do you know about the new book on Analytic Combinatorics by Flajolet ? It appears to answer these questions quite nicely, by actually delving into the analysis side of things.

The link to the book is here, and I wrote about a related matter here.

October 25, 2007 at 10:40 PM
Michael Lugo said...

Suresh,

I know about that book (I think I've even mentioned it a few times before), and I've found it quite interesting.

October 26, 2007 at 4:39 AM
Mitch said...

I never saw this until looking for gf examples in the Schaum outline for Combinatorics (not the Finite or Discrete math one) by Balakrishnan.

Isabel wrote:

I'm not sure how useful it is to know this, though... I can't think of too many times where I had an exponential generating function for some sequence and thought "oh, if only I had the ordinary generating function."

Like with any equation, it can be cool or useful (or both if you're lucky). I think this is useful if you find one kind of symbol easier to manipulate than the other. That is, I personally find rational functions easier to manipulate and ogfs tend to be rational. Of course this is hypothetical since I don't think I've ever -had- to convert one to the other.

dimpase said...

Combinatorics people never seem to know enough analysis.

In defense of such people, a lot of combinatorics is an attempt to get -away- from analysis, emphasizing finitary reasoning. That said, ...

Indeed, I don't recall this formula mentioned in any standard texts on generatingfunctionology.

...that's exactly the first source (Wilf's book, chapter 4) that I would first go to for a start on using analysis for combinatorial problems. And then Flajolet and Sedgewick.

October 29, 2007 at 7:24 AM
Michael Lugo said...

Mitch,

I agree that rational generating functions are the easiest ones to manipulate.

and I don't recall having to ever convert between the two types of generating functions; there are some situationss for which EGFs are natural and some for which OGFs are natural. (This is roughly the distinction between "labeled" and "unlabeled" combinatorial objects -- or at least for me it is -- because multiplication of OGFs corresponds to an unlabeled product and multiplication of EGFs corresponds to a labeled product. But if you've read Flajolet and Sedgewick you know this.)

Mitch wrote:

"In defense of such people, a lot of combinatorics is an attempt to get -away- from analysis, emphasizing finitary reasoning. That said, ..."

the problem with that is that often one can't get *exact* answers and would at least like asymptotic answers, and viewing generating functions as analytic objects seems to be the best way to go about that.

October 29, 2007 at 9:46 AM

Post a Comment

Subscribe to: Post Comments (Atom)