The n-Category Café

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 $n$ elements have? A derangement is a bijection

$$f: S \to S$$

with no fixed points, i.e. no points $x$ with $f(x) = x$. There is just one derangement of $S = \{0,1\}$, namely the function $f$ with

$$f(0) = 1, \qquad f(1) = 0$$

There are 2 derangements of $S = \{0,1,2\}$ — can you see what they are? How many derangements are there of a 5-element set? We’ll see the answer soon. This is a typical sort of combinatorics question.

But what does counting have to do with category theory? The category of finite sets, $\mathsf{FinSet}$, has

• finite sets as objects
• functions between these as morphisms

What we count, ultimately, are finite sets. Any object $S \in \mathsf{FinSet}$ has a cardinality ${|S|}\in \mathbb{N},$ so counting a finite set simplifies it to natural number, and the key feature of this process is that

$$S \cong T \iff {|S|}= {|T|}$$

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 $D$. A $D$-structure on a finite set $S$ is simply a derangement $f: S \to S.$ We write $D(S)$ for the set of all derangements of $S.$ We would like to know ${|D(S)|}$ for all $S \in \mathsf{FinSet}.$

Example 2. There is a species of permutations, called $P$. A $P$-structure on $S \in \mathsf{FinSet}$ is a bijection $f: S \to S$. We know

$${|P(S)|}= {|S|}!$$

We often use $n$ interchangeably for a natural number and a standard finite set with that many elements:

$$n = \{0,1, \dots, n-1 \}$$

With this notation

$${|P(n)|}= n!$$

But what exactly is a species?

Definition. Let $\mathsf{E}$ be the category where

• an object is a finite set
• a morphism is a bijection between finite sets

Definition. A species is a functor $F: \mathsf{E} \to \mathsf{Set}.$ A tame species is a functor $F: \mathsf{E} \to \mathsf{FinSet}.$

Any tame species has a generating function, which is actually a formal power series $\widehat{F} \in \mathbb{R}[[x]],$ given by

$$\displaystyle{ \widehat{F} = \sum_{n \ge 0} \frac{ {|F(n)|}}{n!} x^n }$$

Example 3. We can compute the generating function of the species of permutations:

$$\displaystyle{ \widehat{P} = \sum_{n \ge 0} \frac{n!}{n!} x^n = \frac{1}{1 - x} }$$

Example 4. Given two species $F$ and $G$ there is a species $F \cdot G$ defined as follows. To put an $F \cdot G$-structure on a finite set $S$ is to choose a subset $T \subseteq S$ and put an $F$-structure on $T$ and a $G$-structure on $S - T$. We thus have

$$\widehat{F \cdot G} = \sum_{n \ge 0} \frac{ {|(F \cdot G)(n)|}}{n!} x^n$$

$$= \sum_{n \ge 0} \sum_{0 \le k \le n} \binom{n}{k} {|F(k)|} {|G(n-k)|} \frac{x^n}{n!}$$

$$= \sum_{n \ge 0} \sum_{k \ge 0} \frac{ {|F(k)|}}{k!} \frac{|G(n-k)|}{(n-k)!} x^n$$

$$= \sum_{k \ge 0} \sum_{\ell \ge 0} \frac{ {|F(k)|}}{k!} \frac{ {|G(\ell|}}{\ell!} x^k x^\ell$$

$$= \widehat{F} \widehat{G}$$

Example 5. There is a species $\text{Exp}$ such that every finite set has a unique $\text{Exp}$-structure! We thus have

$${|\text{Exp}(S)|}= 1$$

for all $S \in \mathsf{FinSet}$, so

$$\widehat{Exp} = \sum_{n \ge 0} \frac{1}{n!} x^n = \exp x$$

That’s why we call this boring structure an $\text{Exp}$-structure. I like to call $\text{Exp}$ being a finite set. Every finite set has the structure of being a finite set in exactly one way.

Example 6. Recall that a $D$-structure on a finite set is a derangement of that finite set. To choose a permutation $f: S \to S$ of a finite set $S$ is the same as to choose a subset $T \subset S$, which will be the set of fixed points of $f$, and to choose a derangement of $S - T$. Thus by Example 4 we have

$$P \cong \text{Exp} \cdot D$$

and also

$${|P|}= {|\text{Exp}|}\cdot {|D|}$$

so by Example 3 and Example 5 we have

$$\frac{1}{1 - x} = \exp(x) {|D|}$$

so

$${|D|}= \frac{e^{-x}}{1 - x}$$

or

$$\sum_{n \ge 0} \frac{ {|D(n)|}}{n!} x^n = \frac{e^{-x}}{1 - x}$$

$$= \left(1 - x + \frac{x^2}{2!} - \frac{x^3}{3!} + \frac{x^4}{4!} - \cdots \right)(1 + x + x^2 + x^3 + x^4 + \cdots )$$

From this it’s easy to work out ${|D(n)|}$. I’ll do the example of $n = 5$. If you think about the coefficient of $x^5$ in the above product, you’ll see it’s

$$1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!}$$

So we must have

$$\frac{ {|D(5)|}}{5!} = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!}$$

or

$$\begin{array}{ccl} {|D(5)|}&=& 5! \left( \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} \right) \\ &=& 3 \cdot 4 \cdot 5 - 4 \cdot 5 + 5 - 1 \\ &=& 60 - 20 + 5 - 1 \\ &=& 44 \end{array}$$

In general we see

$${|D(n)|}= n! \left(\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \cdots + \frac{(-1)^{n} }{n!} \right)$$

But we can go further with this… and I’ll ask you to go further in this homework:

Exercise 1. Do the problems here:

• Let’s get deranged!

The category of species

You’ll notice that above I said there was an isomorphism

$$P \cong \text{Exp} \cdot D$$

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

$$F : \mathsf{E} \to \mathsf{Set}$$

where $\mathsf{E}$ 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 $\mathsf{C}$ and $\mathsf{D}$, let the functor category $\mathsf{D}^\mathsf{C}$ be the category where

• an object is a functor $F: \mathsf{C} \to \mathsf{D}$
• morphism $\alpha : F \Rightarrow G$ 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 $\mathsf{Set}^\mathsf{E}$. The category of tame species is $\mathsf{FinSet}^\mathsf{E}$.

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, $P$. We said that for any object $S \in \mathsf{E}$, $P(S)$ is the set of permutations of $S$. But to make $P$ into a functor we also need to say what it does on morphisms of $\math{E}$. That is, given a bijection $f: S \to S'$ and a permutation $g \in F(S)$ we need a way to get a permutation $F(f)(g): S' \to S'$. Figure out the details and then show that $P : \mathsf{E} \to \mathsf{Set}$ obeys the definition of a functor:

$$P(f \circ g) = P(f) \circ P(g)$$

for any composable pair of bijections $g: S \to S', f: S' \to S''$, and

$$P(1_S) = 1_{P(S)}$$

Exercise 3. Show that there is a species $L$, the species of linear orderings, such that an $L$-structure on $S \in \mathsf{FinSet}$ is a linear ordering on $S$. In other words: first let $L(S)$ be the set of linear orderings. Then for any bijection $f: S \to S'$ define a map $L(f): L(S) \to L(S')$ that sends linear orderings of $S$ into linear orderings of $S'$. Then show that $L: \mathsf{E} \to \mathsf{Set}$ obeys the definition of a functor.

Exercise 4. Now show there is no natural isomorphism $\alpha : P \to L$. However we have

$${|P(S)|}= {|L(S)|}= {|S|}!$$

for any finite set $S$, so $P$ and $L$ have the same generating function:

$$\widehat{P} = \widehat{L}$$

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.