What's the difference between EGF & OGF?

Question

I am learning about generating function now, and I am quite confused about where to use EGF and where to use OGF. You know, I could do the exercises following each section, but if there are some mixed exercises, I often don't know whether I should choose OGF or EGF...

In addition, I read this article just now, and I feel also confused about some words in it. Qiaochu said, "In the language of exponential generating functions, differentiation corresponds to a shift in index (this is what we're really going after) and the above($s^n=s\times s^{n-1}$) is equivalent to the identity $\frac{d}{dx} e^{sx}=se^{sx}$." And I don't know how to understand that they are "equivalent".

Thanks in advance.

Answer 1

If you don't know which one to use, then try one and, if it doesn't work, try the other. Over time you will develop a sense of which one is more likely to work on any given problem.

The good thing about math problems is that if something you try doesn't work, you haven't broken anything. No repairs are necessary, no bills to pay, no one gets hurt; you just try something else.

Answer 2

If you are interested in counting problems in particular, it is often the case that OGF's provide a simpler way to handle selections or distributions, while EGF's provide a simpler way to calculate arrangements or restricted permutations.

Answer 3

Last fall I took a course on analytic combinatorics at my school where we covered both OGF's and EGF's extensively. The main difference between the two is a natural one. OGF's are very good at handling combinatorics of unlabelled objects. EGF's are the choice when dealing with objects in the labelled universe. This is mostly because if you have $n$ objects, you can permute their labels in $n!$ ways if there are no other restrictions.

Also, there is a practical reason that I think Qiaochu talked about. If the number of objects $a_n$ of size $n$ grows like $n!$ times other factors, using an EGF clears the $n!$. In fact, suppose that you have a sequence $\{c_n\}_{n=0}^{\infty}$ of "nice" numbers. Then, for a sequence $\{a_n\}_{n=0}^{\infty}$ you can define the generating function (maybe we can call it an AGF)

$$A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{c_n}$$

which has the nice property that if $a_n = c_n$ for all $n$, then

$$A(x) = \frac{1}{1-x}.$$

As long as a function like $C(x) = \sum_{n=0}^{\infty} x^n/c_n$ has some nice properties, I think it would be worthwhile to use it, especially if your generating function involves objects that grow similarly to $c_n$ and you want to make a comparison. At least, this is the way I like to think about them.