How are combinatorial classes and combinatorial species related?

Question

I am reading through Analytic Combinatorics by Flajolet and Sedgewick and I feel pretty confident with my understanding of classes and how they relate to EGFs. However recently I encountered the concept of combinatorial species, and it seems like both concepts essentially do the same thing in relation to EGFs. I'm wondering what is the relation between combinatorial species and combinatorial classes?

For example I would like to know if there is some big difference I'm missing, if there is some advantage to using one over the other, or if one is more general than the other. If both concepts are analogous, then are they just different ways to formalize the same thing, or is there some historical reason why they were both developed?

Thank you for helping my understanding.

Edit: By classes I mean labelled classes. Sorry for the unclear wording.

Answer 1

Combinatorial classes are for unlabeled objects, while combinatorial species are for labeled objects. The two methods are not analogous. You say that "classes" are associated with EGF's, and I object to that phrasing because it is unclear. Normally, combinatorial classes are naturally associated with OGF's. However, labelled classes are a special type of class, and it is true that every labelled class is associated with an EGF.

Combinatorial classes

Combinatorial classes were covered in chapter 1 of Flajolet and Sedgewick. Combinatorial classes associate, to each integer $n$, a finite set, $A_n$, which is thought of as the set of objects with size $n$. There are operations for building new classes, including sum, product, SEQ, etc. Importantly, each combinatorial class is associated with an ordinary generating function, in a way such that the operations on classes play corresponding to alebraic operations on the associated OGF's.

Combinatorial species

Combinatorial species are essentially the same thing as labelled classes, which were covered in chapter 2 of Flajolet and Sedgewick.

• Flajolet and Sedgewick define a labelled class to be a combinatorial class consisting of "well-labeled objects", meaning that each $A_n$ is a set of graphs on the vertex set $\{1,\dots,n\}$. The authors define operations on these labelled classes, such as the labeled product, in a complicated way.

• Combinatorial species are defined in a more general, but equivalent, way. A combinatorial species, $\mathcal C$, associates to every set, $A$, another set, $\mathcal C_A$. For example, the species of permutations associates each set $A$ to the set of bijections from $A$ to itself. The only requirements are that, for all sets $A$ and $B$, $|A|=|B|\implies |\mathcal C_A|=|\mathcal C_B|$, and $A\neq B\implies \mathcal C_A\cap \mathcal C_B=\varnothing$. You can also describe this as a functor from the category ${\bf Set}_{\cong}$ to itself, where ${\bf Set}_{\cong}$ is the category of sets where the only morphisms are bijections. This also has a labelled product (and all the same other operations). Namely, given combinatorial species $\mathcal A$ and $\mathcal B$, we say that $\mathcal C=\mathcal A\star \mathcal B$ if, for all sets $Z$, $$\mathcal C_Z=\bigcup_{X,Y\,:\,X\sqcup Y=Z}\mathcal A_X \times \mathcal B_Y$$

Importantly, it is labelled structures and combinatorial species which are naturally associated with exponential generating functions, such that the labelled product of two labelled structures (or species) corresponds the algebraic product of the EGF's.

Answer 2

Here I refer to the two books:

• Analytic Combinatorics by P. Flajolet and R. Sedgewick and

• Combinatorial Species and Tree-Like Structures by F. Bergeron, G. Labelle and P. Leroux.

In Analytic Combinatorics the authors define combinatorial classes for both, labelled as well as unlabelled objects. We find

• Definition I.4: The ordinary generating function (OGF) of a sequence $(A_n)$ is the formal power series \begin{align*} A(z)=\sum_{n=0}^{\infty}A_nz^n \end{align*} The ordinary generating function (OGF) of a combinatorial class $\mathcal{A}$ is the generating function of the numbers $A_n=\mathrm{card}\left(\mathcal{A}_n\right)$. Equivalently, the OGF of class $\mathcal{A}$ admits the combinatorial form \begin{align*} A(z)=\sum_{a\in\mathcal{A}}z^{|a|} \end{align*}

In the next chapter, section II.1 where labelled structures are introduced we can read:

• In order to count labelled objects, we appeal to exponential generating functions.
• Definition II.1: The exponential generating function (EGF) of a sequence $\left(A_n\right)$ is the formal power series \begin{align*} A(z)=\sum_{n\geq 0}A_n\frac{z^n}{n!} \end{align*} The exponential generating function (EGF) of a class $\mathcal{A}$ is the exponential generating function of the numbers $A_n=\mathrm{card}\left(\mathcal{A}_n\right)$. Equivalently, the EGF of a class $\mathcal{A}$ is \begin{align*} A(z)=\sum_{n\geq 0}A_n\frac{z^n}{n!}=\sum_{a\in\mathcal{A}}\frac{z^{|a|}}{|a|!}. \end{align*}

We see, combinatorial classes are defined in the context of unlabelled objects where we calculate using OGF as well as in the context of labelled objects where we calculate using EGF. Combinatorial species are a framework, a theoretical basis for these combinatorial classes, for both unlabelled as well as labelled objects. Note, the book description of Combinatorial Species starts with:

• (CUP Book description:) The combinatorial theory of species, introduced by Joyal in 1980, provides a unified understanding of the use of generating functions for both labelled and unlabelled structures and as a tool for the specification and analysis of these structures.

clearly stating that combinatorial species are used for both, labelled and unlabelled structures. The MAA review of Analytic Combinatorics indicates that combinatorial species are a theoretical basis for the combinatorial classes by stating:

• (MAA Review) ... The authors explain the mechanics of determining ordinary and exponential generating fucntions for different combinatorial constructions, using ideas from the theory of species, a powerful method that unifies apparently disparate combinatorial objects. ...

P. Flajolet and R. Sedgewick also refer to A. Joyals combinatorial species in both sections I.7 Perspective and II.7 Perspective for unlabelled as well as for labelled structures.

Note: The relationship between Analytic combinatorics and Combinatorial Species is considered for example in Algorithms for Combinatorial Systems: Between Analytic Combinatorics and Species Theory by C. Pivoteau, B. Salvy and M. Soria.