Combinatorics, Lecture 3 (3 Oct 2019)

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 \mathsf{Set}^\mathsf{S}, with species G\colon\mathsf{S}\to\mathsf{Set} as objects and natural transformations \alpha \colon G \Rightarrow G' as morphisms.

There is a subcategory of \mathsf{Set}^\mathsf{S} where the objects are finite species, denoted \mathsf{F}^\mathsf{S}.

We’ve talked about functors in this class before, but not yet natural transformations. Recall: given categories \mathcal{C} and \mathcal{D}, a functor G \colon \mathcal{C} \to \mathcal{D} sends objects c \in \mathcal{C} to objects G(c) \in \mathcal{D}, and morphisms f \colon c\to c' in \mathcal{C} to morphisms G(f) \colon G(c) \to G(c') in \mathcal{D} such that G(g \circ f) = G(g) \circ G(f) and G(1_c) = 1_{G(c)}.

If G,H \colon \mathcal{C} \to \mathcal{D} are functors, then a natural transformation \alpha \colon G \Rightarrow H assigns to each object c \in \mathcal{C} a morphism \alpha_c \colon G(c) \to H(c) in \mathcal{D}, such that the naturality square

commutes. If all the components \alpha_c are invertible, then we say that \alpha is a natural isomorphism.

Proposition: If \alpha is a natural isomorphism then there exists a natural transformation \alpha^{-1} given by (\alpha^{-1})_c=(\alpha_c)^{-1}.

Theorem: If \mathcal{C} and \mathcal{D} are categories then there is a category \mathcal{D}^\mathcal{C} whose objects are functors \mathcal{C}\to\mathcal{D} and whose morphisms are natural transformations, with composition \beta\circ\alpha\colon G\Rightarrow J of \alpha\colon G\Rightarrow H and \beta \colon H \Rightarrow J given by (\beta \circ \alpha)_c = \beta_c \circ \alpha_c.

Example: Let P\colon\mathsf{S}\to\mathsf{F} 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 B : \mathsf{S} \to \mathsf{F} 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: P \cong B, i.e.\ the functors are naturally isomorphic

Proof idea: We need bijections \alpha_X : P(X) \xrightarrow{\sim} B(X) for X \in \mathsf{S} which are natural.

Given the tree in B(5) from the above example, let’s construct the corresponding element of P(5). 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 5+1 vertices, label the top-most one `root’, and the others in the same order as the leaves of our element of B(5).

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 G, H : \mathsf{S} \to \mathsf{F} be finite species. If G \cong H then |G| = |H|.

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 \alpha : G \Rightarrow H, then there’s a bijection \alpha_x : G(X) \xrightarrow{\sim} H(X) for all X \in \mathsf{S}, so |G(X)| = |H(X)| for all X, thus

|G|(x) = \sum \frac{|G(n)|}{n!} x^n =  \sum \frac{|H(n)|}{n!} x^n = |H|(x).

In Lecture 4, we’ll begin to see how we can actually use species and their generating functions to solve problems in combinatorics.

One thought on “Combinatorics, Lecture 3 (3 Oct 2019)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s