# Differences Exponential and Ordinary Generating Functions

I am trying to understand conceptually the differences between ordinary generating functions (OGF$=1+x+x^2+\ldots$ ) and exponential generating functions (EGF$=1+x+\frac{x^2}{2!}+\ldots$ ) when it comes to counting objects (e.g. how labeling and ordering come into play). The easiest way for me to understand the differences is through understanding interpretations of "analogous" representations. Are the following representations correct? Are they good examples for understanding the differences of the generating functions? Are there other good \ better examples?

(a) OGF: Representing an $n$ letter sequence using 1 letter $$1+x+x^2+\ldots$$

EGF: Representing an $n$ letter word using 1 letter $$1+x+\frac{x^2}{2!}+\ldots$$

(b) OGF: Representing an $n$ letter sequence where each letter can be one of $k$ possible letters and the order of the letters within the sequence does not matter $$(1+x+x^2+\ldots)^k$$

EGF: Representing an $n$ letter word where each letter can be one of $k$ possible letters $$(1+x+\frac{x^2}{2!}+\ldots)^k$$

(c) OGF: Representing a sentence with $m$ words where each word has $n$ letters where each letter can be one of $k$ possible letters and the order of the words in the sentence does not matter and the order of the letters within a word does not matter $$(1+x+x^2+\ldots)+(1+x+x^2+\ldots)^2+\ldots$$

EGF: Representing a sentence with $m$ words where each word has $n$ letters where each letter can be one of $k$ possible letters (order matters in the sentence and in each word) $$(1+x+\frac{x^2}{2!}+\ldots)+(1+x+\frac{x^2}{2!}+\ldots)^2+\ldots$$

(d) others?

• Ordinary generating functions and exponential generating functions are just different ways to represent the same sequence of numbers. Multiplying two generating functions corresponds to different operations on the two respective sequences, so one may be more useful than the other depending on your application. Apr 10, 2014 at 12:15
• @ShreevatsaR, sometimes the form of a recurrence makes one more suitable than the other, with little relation to anything else. Apr 10, 2014 at 19:49
• @vonbrand: What I meant is that usually the fact that one is more suitable than the other (e.g. using OGFs for unlabelled structures and EGFs for labelled structures) arises from the fact that multiplying OGFs corresponds to ordinary convolution, and multiplying EGFs to binomial convolution (corresponding to the operations of product and labelled (star) product, in Flajolet&Sedgewick's terms). Apr 11, 2014 at 2:35
• @vonbrand: Of course, one may have a recurrence relation that doesn't transparently arise from any operations on combinatorial structures in the Flajolet&Sedgewick sense, where one turns out to be more useful than the other. I agree with that too, but often in practice there's some labelled-or-unlabelled combinatorial structure underneath, or at least corresponding to the same recurrence relation. Apr 11, 2014 at 2:38
• Another difference is that ordinary vs exponential changes where/if the series converges (generating functions are most effective when they converge for some nonzero $x$'s). For example, take the series $a_n = n!$, the ordinary generating function $\sum_n n! x^n$ only converges for $x=0$, but the exponential generating function $\sum_n n! \cdot\frac{x^n}{n!} = \sum_n x^n = 1/(1-x)$ converges for $|x| < 1$. Mar 10, 2021 at 17:14