A few days ago I asked a question about the difference between the definition of classes of structures and combinatorial classes.
I have been told that a combinatorial class refers to "unlabeled objects" and to this an ordinary generating function is associated.
In the case of classes of structures, it refers to "labeled objects" and to this an exponential generating function is associated.
According to the bibliography that I am consulting (Analytic Combinatorics – Philippe Flajolet Robert Sedgewick, Introduction to Combinatorial Enumeration – David G. Wagner) this makes sense.
My question is, why for this? The authors in the notes usually write (not literal) "a combinatorial structure corresponds to an ordinary generating function", "a collection of labeled objects is assigned an exponential generating function".
In short, there is a formal justification for why to collection of labeled objects is assigned an exponential generating function and to collection of unlabeled objects is assigned an ordinary generating function?
In which case does the sequence of numbers have both generating functions, or in which case are they useful?
Best Answer
$ \newcommand\c[1]{\mathcal{#1}} $There is a good reason why we use OGF's for unlabeled structures and EGF's for labeled structures. The reason is that the multiplication for OGF's corresponds exactly the to the product for unlabeled structures, while the multiplication for EGF's corresponds to the product for labeled structures.
Unlabeled products. Let $(\mathcal A,|\cdot|_{\mathcal A})$ and $(\mathcal B,|\cdot|_{\mathcal B})$ be two unlabeled structures. The cartesian product $\c A\times \c B$ is also an unlabeled structure, with size function $$ |(A,B)|_{\c A\times \c B}=|A|_{\c A}+|B|_{\c B} $$ Let $a_n,b_n,c_n$ be the size sequences for $\c A,\c B,$ and $\c A\times \c B$, respectively. That is, $a_n=|\{A\in \c A\mid |A|_{\c A}=n\}|$, and analogously for $b_n$ and $c_n$. A consequence of these definitions is $$ c_n=\sum_{k=0}^n a_k b_{n-k} $$ Letting $A(x)=\sum_{n\ge 0}a_nx^n$ be the OGF for $\c A$, and similarly for $B(x)$ and $C(x)$, this quickly implies that $C(x)=A(x)\cdot B(x)$. Therefore, the OGF of the product is the product of the OGF's, which is a beautiful and fruitful correspondence.
Labeled products. Recall that a labeled structure is described by a function $\c A$, which takes in a finite set $X$ and returns a different finite set $\c A_X$. For example: the labeled structure of permutations is described by $X\mapsto \{\text{bijections on $X$}\}$. The only axioms required are $|X|=|Y|\implies |\c A_X|=|\c A_Y|$, and $X\neq Y\implies \c A_X \cap \c A_Y=\varnothing$.
There is also a natural notion of product $\c A\otimes \c B$ of two labeled structures. To each set $Z$, the set of $(\c A\otimes \c B)$-structures on $Z$ is defined to be $$ (\c A\otimes \c B)_Z=\bigcup_{X\sqcup Y=Z} \c A_X \times \c B_Y $$ The meaning of $X\sqcup Y=Z$ in the subscript is that $(X,Y)$ ranges over all pairs of sets which are disjoint and whose union is $Z$. In words, to choose the product structure, you partition $Z$ into two parts, then put an $\c A$-structure on the first, then independently put a $\c B$-structure on the second. This product really is natural; for example the labeled structure "permutations with two cycles" is the product of "cyclic permutations" with itself.
A consequence of this definition is that if $a_n,b_n,c_n$ are the size enumerators for $\c A, \c B,$ and $\c A\otimes \c B$, meaning that $a_n=|\c A_{\{1,\dots,n\}}|$ and similarly for $b_n$ and $c_n$, then $$ c_n=\sum_{k=0}^n \binom{n}k a_k b_{n-k} $$ This further implies that if $A(x)=\sum_{n\ge 0} a_n \frac{x^n}{n!}$ is the EGF for $\c A$, and $B(x)$ and $C(x)$ are the EGF's for $\c B$ and $\c A\otimes \c B$, then $C(x)=A(x)\cdot B(x)$. Again, the EGF of the product of labeled structures is the product of their EGF's.