In spite of having done some exercises, I still find it harder to understand exponential generating function deeply than ordinary generating function. Could someone explain it "deeply"? Or are there any articles on that?
Deep understanding on exponential generating function
-
0I suggest that you either read the book by Bergeron, Labelle and Leroux or that you ask a more precise question. The book might help to convince you that egfs are simpler than ogfs. http://books.google.com/books?id=83odtWY4eogC&printsec=frontcover&dq=labelle+species&hl=de&ei=Cc61TuDANsqWhQfGxOGaBA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CC0Q6AEwAA#v=onepage&q&f=false – 2011-11-06
-
0Hmm. The Wikipedia page on [symbolic combinatorics](http://en.wikipedia.org/wiki/Symbolic_combinatorics) might be helpful, though I suppose you could say it's terse. No doubt user Qiaochu has some posts laying around somewhere or other on this topic. – 2011-11-06
-
1I like "Generatingfunctionology" by Wilf. The 2nd edition can be downloaded from http://www.math.upenn.edu/~wilf/DownldGF.html. The 3rd edition is available from the publisher. – 2011-11-06
-
1Chapter $3$ of Miklós Bóna’s *Introduction to Enumerative Combinatorics* gives a nice introductory sense of the respective contexts in which egf’s and ogf’s are useful. – 2011-11-06
-
5Think of it this way: there are situations where the EGF is simple/easy to manipulate when the OGF is unwieldy or has no closed form, and vice-versa... – 2011-11-06
-
3anon guessed correctly, [here's](http://www.artofproblemsolving.com/blog/10601) an old blog post by Qiaochu somewhat related to this. – 2011-11-06
1 Answers
We typically use ordinary generating functions when counting unlabelled objects and exponentially generating functions when counting labelled objects. For instance combinatorial enumeration of permutations is most convenient analysed by exponential generating functions.
Here I'd like to give an indication which structures do we count when applying the binomial convolution \begin{align*} \sum_{k=0}^n\binom{n}{k}b_kc_{n-k} \end{align*} of two exponential generating functions $B(z)=\sum_{j=0}^\infty b_j \frac{z^j}{j!}$ and $C(z)=\sum_{k=0}^\infty c_k\frac{z^k}{k!}$.
Permutations: We introduce a universe $\mathcal{P}$ of (labelled) permutations. We label the atoms of the permutations of size $n$ as usual with $1,2,\ldots,n$. We also add an empty permutation $\varepsilon$ of length $0$ and consider \begin{align*} \mathcal{P}=\{\varepsilon,1,12,21,123,132,213,231,312,321,\ldots\}\tag{1} \end{align*}
The coefficients $a_n$ of the corresponding exponential generating function $A(z)=\sum_{n=0}^\infty a_n \frac{z^n}{n!}$ give the number $n!$ of permutations of size $n$. We obtain \begin{align*} \color{blue}{A(z)}=\sum_{n=0}^\infty n!\frac{z^n}{n!}=\sum_{n=0}^\infty z^n\color{blue}{=\frac{1}{1-z}} \end{align*}
We observe that generating functions like $\frac{1}{1-z}$ may serve as both, ordinary generating functions \begin{align*} \frac{1}{1-z}=\sum_{n=0}^\infty z^n=\color{blue}{1}+\color{blue}{1}\cdot z+\color{blue}{1}\cdot z^2+\color{blue}{1}\cdot z^3+\cdots \end{align*} to count for instance a sequence of unary words \begin{align*} \mathcal{S}=\{\varepsilon,\bullet,\bullet\bullet,\bullet\bullet\bullet,\ldots\}\tag{2} \end{align*}
as well as exponential generating functions \begin{align*} \frac{1}{1-z}=\sum_{n=0}^\infty n!\frac{z^n}{n!}=\color{blue}{0!}+\color{blue}{1!}\cdot \frac{z}{1!}+\color{blue}{2!}\cdot \frac{z^2}{2!}+\color{blue}{3!}\cdot \frac{z^3}{3!}+\cdots \end{align*} to count permutations according to (1).
Note, the simplicity of the geometric series $\frac{1}{1-z}=1+z+z^2+\cdots$ strongly indicates the universe of permutations is the prototypical structure approachable by exponential generating functions.
Warmup: Multiplicative structure of ordinary generating functions.
We consider $\mathcal{B}=\{\bullet,\bullet\bullet\bullet\},\mathcal{C}=\{\bullet,\bullet\bullet\}$ with corresponding generating functions $B(z)=z+z^3, C(z)=z+z^2$ and obtain due to the multiplicative rule \begin{align*} \color{blue}{\mathrm{card}\left(\mathcal{B}\times \mathcal{C}\right)=\mathrm{card}\left(\mathcal{B}\right)\cdot \mathrm{card}\left(\mathcal{C}\right)} \end{align*} the set $\mathcal{A}=\{(\bullet,\bullet),(\bullet,\bullet\bullet),(\bullet\bullet\bullet,\bullet),(\bullet\bullet\bullet,\bullet\bullet)\}$ and the following relationship \begin{align*} A(z)&=\sum_{a\in\mathcal{A}}z^{|a|}=\sum_{(\beta,\gamma)\in(\mathcal{B}\times\mathcal{C})}z^{|\beta|+|\gamma|} =\left(\sum_{\beta\in \mathcal{B}}z^{|\beta|}\right)\times\left(\sum_{\gamma\in \mathcal{C}}z^{|C|}\right)=B(z)\cdot C(z)\\ A(z)&=z^2+z^3+z^4+z^5\\ &=z^{1+1}+z^{1+2}+z^{3+1}+z^{3+2}=\left(z^1+z^3\right)\times\left(z^1+z^2\right)=(z+z^3)(z+z^2) \end{align*} which follows from distributing products over sums.
Multiplicative structure of exponential generating functions:
In order to cover the binomial convolution $\sum_{k=0}^n\binom{n}{k}b_kc_{n-k}$ of exponential generating functions we will encounter a more sophisticated multiplicative rule for labelled structures. Nevertheless we will do it similarly to the warmup above.
We consider $\mathcal{B}=\{123,213\},\mathcal{C}=\{12\}$ with generating functions $B(z)=2\frac{z^3}{3!}, C(z)=\frac{z^2}{2!}$ and consider the multiplicative rule \begin{align*} \color{blue}{\mathcal{B}\star\mathcal{C}=\bigcup_{\beta\in\mathcal{B},\gamma\in\mathcal{C}}\left(\beta\star\gamma\right)}\tag{3} \end{align*} which is defined as:
- The labelled product (3) of $\mathcal{B}$ and $\mathcal{C}$, denoted $\mathcal{B}\star\mathcal{C}$, is obtained by forming ordered pairs from $B\star C$ and performing all possible order-consistent relabellings.
The last phrase all possible order-consistent relabellings needs to be explained. With the example $\mathcal{B}=\{123,213\}$ and $\mathcal{C}=\{12\}$ we perform a relabeling.
At first we start with a relabelling and select wlog $\mathcal{C}=\{45\}$ by respecting the order ($1<2$, i.e. $4<5$). We now obtain all order-consistent relabellings as follows \begin{align*} \mathcal{B}\star\mathcal{C}&=\bigcup_{\beta\in\mathcal{B},\gamma\in\mathcal{C}}\left(\beta\star\gamma\right)\\ &=\left(\{123\}\star\{45\}\right)\cup\left(\{213\}\star\{45\}\right)\\ &=\{12345,12435,12534,13425,13524,14523,23415,23514,24513,34512\}\tag{4}\\ &\qquad\cup\{21345,21435,21534,31425,31524,41523,32415,32514,42513,43512\}\tag{5}\\ \end{align*}
When looking at the set $\{123\}\star\{45\}$ we can find all order-consistent relabelings as follows: We have to generate permutations of length $5$. We create all $\binom{5}{3}=10$ strings of length $3$ from $\{1,2,3,4,5\}$ which follow the order $1<2<3$. We obtain \begin{align*} \{123,124,125,134,135,145,234,235,245,345\}. \end{align*} Note, that each element in the set above follows the ordering $(\mathrm{smallest} < \mathrm{middle} < \mathrm {largest})$. We complete (4) by concatenating each $3$-element string with a string consisting of the remaining two elements from $\{1,2,3,4,5\}$ following the order $4<5$, i.e. $(\mathrm{smallest} < \mathrm{largest})$. Similarly we build (5) by respecting the order $2<1<3$, i.e. $(\mathrm{middle} < \mathrm{smallest} < \mathrm{largest})$.
We observe from (4), (5):
\begin{align*} |\mathcal{B}\star\mathcal{C}|=2\binom{5}{3}=2\cdot 10=20 \end{align*}
and the relationship with the generating functions $B(z)$ and $C(z)$ is given as \begin{align*} \color{blue}{A(z)}&=B(z)\cdot C(z)=\left(2\cdot \frac{z^3}{3!}\right)\cdot\left(\frac{z^2}{2!}\right)\\ &\,\,\color{blue}{=2\binom{5}{3}\frac{z^5}{5!}} \end{align*}
Hint: This answer is based upon the great presentation of admissible structures in chapter 1 and 2 of Analytic Combinatorics by P. Flajolet and R. Sedgewick.