Lecture 2 here. Thanks again to Tim Hosgood for the beautiful pictures.
The category of species
Last time, we looked at the relationship between species and their generating functions, a formal power series associated to a species which lets you count structures described by the species. Now we’ll take a closer look at species themselves. In particular, there is a category where the objects are species. As is the case in so many branches of math, looking at the category of our main objects of study will be a useful perspective.
There is a category of species, called , with species as objects and natural transformations as morphisms.
There is a subcategory of where the objects are finite species, denoted .
We’ve talked about functors in this class before, but not yet natural transformations. Recall: given categories and , a functor sends objects to objects , and morphisms in to morphisms in such that and .
If are functors, then a natural transformation assigns to each object a morphism in , such that the naturality square
commutes. If all the components are invertible, then we say that is a natural isomorphism.
Proposition: If is a natural isomorphism then there exists a natural transformation given by .
Theorem: If and are categories then there is a category whose objects are functors and whose morphisms are natural transformations, with composition of and given by .
Example: Let be defined as follows. For a finite set X, let P(X) be the set of all ways of performing the following procedure:
- draw a regular (|X|+1)-gon;
- label all but one of the sides with the elements of X;
- triangulate the polygon.
For example, here is an element of P(5):
Example: Let be the species defined as follows: for a finite set X, B(X) is the set of binary, planar, rooted trees whose leaves are equipped with a bijection to X, or X-labelled trees for short. For X=5, B(5) has an element like this:
Theorem: , i.e.\ the functors are naturally isomorphic
Proof idea: We need bijections for which are natural.
Given the tree in from the above example, let’s construct the corresponding element of . We start with a (5+1)-gon.
Rather than labelling sides, we’re going to label vertices that we place just outside of each side of the polygon (except for one that we place inside). So we draw vertices, label the top-most one `root’, and the others in the same order as the leaves of our element of .
Then we draw a copy of our tree inside the polygon.
Finally, we triangulate our polygon by crossing each branch of the tree exactly once.
Theorem: Let be finite species. If then .
Note that the converse is not true! In future lectures, we’ll look at examples of non-isomorphic species with the same generating functions.
Proof: If there’s a natural isomorphism , then there’s a bijection for all , so for all X, thus
In Lecture 4, we’ll begin to see how we can actually use species and their generating functions to solve problems in combinatorics.