2
$\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$
  • $\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$ – ShreevatsaR Apr 10 '14 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 '14 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$ – ShreevatsaR Apr 11 '14 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$ – ShreevatsaR Apr 11 '14 at 2:38
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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