Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
I take it EGF means exponential generating function, OGF means ordinary generating function. –  Gerry Myerson Nov 9 '11 at 23:19
    
You eventually develop a sense of when you should use an OGF, and when you should use an EGF. There's nothing wrong with trying another approach if the first one doesn't pan out, you know. –  J. M. Nov 9 '11 at 23:21
    
@J. M. Thanks, any ideas for my second para.? –  Kou Nov 9 '11 at 23:52
    
Well, if you have $G(x)=a_0+\sum\limits_{k=1}^\infty \frac{a_k x^k}{k!}$, then $G^\prime(x)=\sum\limits_{k=1}^\infty \frac{k a_k x^{k-1}}{k!}=\sum\limits_{k=1}^\infty \frac{a_k x^{k-1}}{(k-1)!}=a_1+\sum\limits_{k=1}^\infty \frac{a_{k+1} x^k}{k!}$... –  J. M. Nov 9 '11 at 23:58

3 Answers 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.

share|improve this answer

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.

share|improve this answer
    
Thanks a lot. Besides, do you have anything to say with my second question that why those two identities could be viewed as equivalent? –  Kou Nov 9 '11 at 23:44

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.