4
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Apr 10, 2014 at 12:15
  • $\begingroup$ @ShreevatsaR, sometimes the form of a recurrence makes one more suitable than the other, with little relation to anything else. $\endgroup$
    – vonbrand
    Apr 10, 2014 at 19:49
  • $\begingroup$ @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). $\endgroup$ Apr 11, 2014 at 2:35
  • $\begingroup$ @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. $\endgroup$ Apr 11, 2014 at 2:38
  • $\begingroup$ 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$. $\endgroup$ Mar 10, 2021 at 17:14

1 Answer 1

1
$\begingroup$

The best explanation of the differences I've seen are in the discussion of the symbolic method, as given by Flajolet and Segdewick in Analytic Combinatorics, and more accessibly by Sedgewick and Flajolet in "Introduction to the Analysis of Algorithms" (Addison Wesley, 2nd edition 2013). This Wikipedia article should be enough to get you going.

$\endgroup$
1
  • 2
    $\begingroup$ I was hoping for something short and sweet - oh well $\endgroup$ Dec 12, 2019 at 16:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .