These are some lecture notes for a 4-hour minicourse I’m teaching at the Summer School on Algebra at the Zografou campus of the National Technical University of Athens. To save time, I am omitting the pictures I’ll draw on the whiteboard, along with various jokes and profoundly insightful remarks. This is just the structure of the talk, with all the notation and calculations.
Long-time readers of the -Category Café may find little new in this post. I’ve been meaning to write a sprawling book on combinatorics using categories, but here I’m trying to explain the use of species and illustrate them with a nontrivial example in less than 1.5 hours. That leaves three hours to go deeper.
Part 2 is here, and Part 3 is here.
Species and their generating functions
Combinatorics, or at least part of it, is the art of counting. For example: how many derangements does a set with elements have? A derangement is a bijection
with no fixed points. We’ll count them in a while.
But what does counting have to do with category theory? The category of finite sets, , has
- finite sets as objects
- functions between these as morphisms
What we count, ultimately, are finite sets. Any object has a cardinality so counting a finite set simplifies it to natural number, and the key feature of this process is that
We’ll count structures on finite sets. A ‘species’ is roughly a type of structure we can put on finite sets.
Example 1. There is a species of derangements, called . A -structure on a finite set is simply a derangement We write for the set of all derangements of We would like to know for all
Example 2. There is a species of permutations, called . A -structure on is a bijection . We know
We often use interchangeably for a natural number and a standard finite set with that many elements:
With this notation
But what exactly is a species?
Definition. Let be the category where
- an object is a finite set
- a morphism is a bijection between finite sets
Definition. A species is a functor A tame species is a functor
Any tame species has a generating function, which is actually a formal power series given by
Example 3. We can compute the generating function of the species of permutations:
Example 4. Given two species and there is a species defined as follows. To put an -structure on a finite set is to choose a subset and put an -structure on and a -structure on . We thus have
Example 5. There is a species such that every finite set has a unique -structure! We thus have
for all , so
That’s why we call this boring structure an -structure. I like to call being a finite set. Every finite set has the structure of being a finite set in exactly one way.
Example 6. Recall that a -structure on a finite set is a derangement of that finite set. To choose a permutation of a finite set is the same as to choose a subset , which will be the set of fixed points of , and to choose a derangement of . Thus by Example 4 we have
and also
so by Example 3 and Example 5 we have
so
or
From this it’s easy to work out . I’ll do the example of . If you think about the coefficient of in the above product, you’ll see it’s
So we must have
or
In general we see
But we can go further with this… and I’ll ask you to go further in this homework:
Exercise 1. Do the problems here:
The category of species
You’ll notice that above I said there was an isomorphism
without ever defining an isomorphism of species! So let’s do that. In fact there’s a category of species.
I said a species is a functor
where is the category of finite sets and bijections. But what’s a morphism between species?
It’s easy to guess if you know what goes between functors: it’s a natural transformation.
Definition. For any categories and , let the functor category be the category where
- an object is a functor
- morphism is a natural transformation.
(We write this with double arrows since a functor was already a kind of arrow, and now we’re talking about an arrow between arrows.)
Definition. The category of species is . The category of tame species is .
Two tame species can have the same generating function but not be isomorphic! You can check this in these exercises:
Exercise 2. In Example 2 we began defining the species of permutations, . We said that for any object , is the set of permutations of . But to make into a functor we also need to say what it does on morphisms of . That is, given a bijection and a permutation we need a way to get a permutation . Figure out the details and then show that obeys the definition of a functor:
for any composable pair of bijections , and
Exercise 3. Show that there is a species , the species of linear orderings, such that an -structure on is a linear ordering on . In other words: first let be the set of linear orderings. Then for any bijection define a map that sends linear orderings of into linear orderings of . Then show that obeys the definition of a functor.
Exercise 4. Now show there is no natural isomorphism . However we have
for any finite set , so and have the same generating function:
Thus, you’ve found nonisomorphic tame species with the same generating function!
This may make you sad, because you might hope that you could tell whether two species were isomorphic just by looking at their generating function. But if that were true, species would contain no more information than formal power series. In fact they contain more! Species are like an improved version of formal power series. And there’s not just a set of them, there’s a category of them.