The n-Category Café

Last time I began explaining how a chunk of combinatorics is categorified ring theory. Every structure you can put on finite sets is a species, and the category of species is the free symmetric 2-rig on one object, just as the polynomial ring $\mathbb{Z}[x]$ is the free commutative ring on one generator.

In fact it’s almost true that every species gives an element of $\mathbb{Z}[x]$! You should think of mathematics as wanting this to be true. But it’s not quite true: in fact every tame species has a generating function, which is an element of $\mathbb{R}[[x]]$, a ring that’s a kind of ‘completion’ of $\mathbb{Z}[x]$. There’s a lot to be said about the slippage here, and why it’s happening, but there’s not time for such abstract issues now. Instead, let’s see what we can do with this analogy:

Just as $\mathbb{Z}[x]$ is the free commutative ring on one generator, the category of species $\mathsf{Set}^\mathsf{E}$ is the free symmetric 2-rig on one generator.

Substitution of species

$\mathbb{Z}[x]$ is the free commutative ring on one generator, namely $x$. Thus for any element $P \in \mathbb{Z}[x]$, there’s a unique ring homomorphism

$$f: \mathbb{Z}[x] \to \mathbb{Z}[x]$$

sending $x$ to $P$:

$$f(x) = P$$

What is this homomorphism $f$? It sends $x$ to $P$, so it must send $x^2$ to $P^2$, and it must send $x^2 + 3x + 1$ to $P^2 + 3P + 1$, and so on. Indeed it sends any polynomial $Q$ to $Q(P)$, or in other words $Q \circ P$:

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

So, we’re seeing that we can compose elements of $\mathbb{Z}[x]$, or substitute one in another.

The same thing works for species! Since the category of species, $\mathsf{Set}^\mathsf{E}$, is the free symmetric 2-rig on one generator $X$, for any species $P \in \mathsf{Set}^\mathsf{E}$ there’s a unique map of symmetric 2-rigs

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

sending $X$ to $P$:

$$F(X) = P$$

And following the pattern we saw for polynomials, we can say

$$F(Q) = Q \circ P$$

But this time we are defining the $\circ$ operation by this formula, since we didn’t already know a way to compose species, or substitute one in another. But it’s very nice:

Theorem. If $Q$ and $P$ are species, to put a $Q \circ P$-structure on a finite set $S$ is to choose an unordered partition of $S$ into nonempty sets $T_1, \dots, T_n$:

$$S = T_1 \cup \cdots T_n , \qquad i \ne j \implies T_i \cap T_j = \emptyset$$

and put a $P$-structure on $\{1, \dots, n\}$ and a $Q$-structure on each set $T_i$. Moreover

$$\widehat{Q \circ P} = \widehat{Q} \circ \widehat{P}$$

if the constant term of $\widehat{P} \in \mathbb{R}[[x]]$ vanishes.

Let’s illustrate this with an easy example and then try some a more interesting example.

Example 7. Remember from Example 5 that $\Exp$ is our name for the species is being a finite set—every finite set has this structure in exactly one way. We call it $\text{Exp}$ because its generating function is the power series for the exponential function:

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

Let $\frac{X^2}{2!}$ be the species being a 2-element set: every set with 2 elements has this structure in exactly one way, while a set with any other number of elements cannot have this structure. We give it this funny name because

$$\widehat{\frac{X^2}{2!}} = \sum_{n \ge 0} \frac{a_n}{n!} x^n$$

where

$$a_n = \left\{ \begin{array}{ccl} 1 & \text{ if } & n = 2 \\ 0 & \text{ if} & n \ne 2 \end{array} \right.$$

so

$$\widehat{\frac{X^2}{2!}} = \frac{x^2}{2}$$

Now let’s compose these species, and let

$$F = \text{Exp} \circ \frac{X^2}{2!}$$

By the theorem, to put an $F$-structure on $S$ is to partition $S$ into nonempty parts, put an $\Exp$-structure on the set of parts, and put an $\frac{X^2}{2!}$-structure on each part. But there’s just one way to put an $\Exp$-structure on the set of parts. So, putting an $F$-structure on $S$ is the same as partitioning $S$ into parts of cardinality $2$.

How many ways are there to do that? We could figure it out, but let’s use the theorem, which says

$$\widehat{F} = \widehat{\text{Exp}} \circ \widehat{\frac{X^2}{2!}}$$

and thus

$$\widehat{F} = e^{x^2/2}$$

so

$$\begin{array}{ccl} \displaystyle{ \sum_{n \ge 0} \frac{|F(n)|}{n!} } &=& e^{x^2/2} \\ \\ &=& \displaystyle{ 1 + (x^2/2) + \frac{(x^2/2)^2}{2!} + \frac{(x^2/2)^3}{3!} + \cdots } \\ \\ &=& \displaystyle{ \sum_{k \ge 0} \frac{1}{2^k k!} x^{2k} } \end{array}$$

So, we see that if $n = 2k$ is even,

$$|F(n)| = \frac{n!}{2^k k!}$$

So this is the number of $F$-structures on an $n$-element set. We can check our work if we know a bit about symmetries and counting. The group $S_n$ acts transitively on the set $F(n)$ of ways to partition an $n$-element set into 2-element parts. The subgroup that fixes any such partition is $S_k \times (\mathbb{Z}/2)^k$, since we can permute the $k$ parts or permute the 2 elements in each part. Thus,

$$|F(n)| = \frac{n!}{2^k k!}$$

The generating function method is nice because we can just turn the crank. And as we’ll see, we can use it to solve harder problems.

Example 8. How many ways can we partition an $n$-element set into nonempty parts? This is called the $n$th Bell number, $b_n$. Let’s see if we can calculate it!

Let $\text{Part}$ be the species of partitions. I claim there are species $\text{Exp}$ and $\text{NE}$ such that

$$\text{Part} \cong \text{Exp} \circ \text{NE}$$

$\text{Exp}$ is our old friend ‘being a finite set’. $\text{NE}$ is the species being a nonempty finite set. To partition a finite set into nonempty finite sets is to partition it into sets, put a $\text{Exp}$-structure on the set of parts, and put an $\text{NE}$-structure on each part. That gives the isomorphism above!

We know that

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

and similarly

$$\widehat{\text{NE}} = \sum_{n \ge 1} \frac{x^n}{n!} = \exp(x) - 1$$

Thus by the theorem,

$$\widehat{\text{Part}} = \widehat{\text{Exp}} \circ \widehat{\text{NE}} = e^{e^x - 1}$$

So by the definition of the Bell numbers,

$$\sum_{n \ge 0} \frac{b_n}{n!} x^n = e^{e^x - 1}$$

This is not quite an explicit formula for the Bell numbers, but it’s almost as good! Let’s use it to calculate the first few Bell numbers. We’ll work out the power series for $e^{e^x - 1}$ only up to order $x^3$:

$$\begin{array}{ccl} e^{e^x - 1} &=& \exp\left( x + \frac{x^2}{2} + \frac{x^3}{6} + \cdots \right) \\ \\ &=& 1 + \left( x + \frac{x^2}{2} + \frac{x^3}{6} + \cdots \right) + \frac{1}{2} \left( x + \frac{x^2}{2} + \cdots \right)^2 + \frac{1}{6} x^3 + \cdots \\ \\ &=& 1 + x + \frac{2}{2!} x^2 + \frac{5}{3!} x^3 + \cdots \end{array}$$

This gives

$$b_0 = 1, \quad b_1 = 1, \quad b_2 = 2, \quad b_3 = 5$$

which we can easily confirm. So it works!

There is a lot more one can do with species. Luckily there are some free books that will take you further:

• François Bergeron, Gilbert Labelle, and Pierre Leroux, Introduction to the Theory of Species of Structures.

• Phillipe Flajolet and Robert Sedgewick, Analytic Combinatorics.

• Herbert S. Wilf, Generatingfunctionology.

Linear species

Finally, let me just conclude by mentioning a variant. We can define the category of linear species to be $\mathsf{Vect}^\mathsf{E}$ where $\mathsf{Vect}$ is the category of complex vector spaces and linear maps. So, it’s just like the category of species but with $\mathsf{Set}$ replaced by $\mathsf{Vect}$.

It turns out that like the category of species, the category of linear species is a 2-rig. We call the addition $\oplus$ because now, given two linear species $F, G : \mathsf{E} \to \mathsf{Vect}$, we define

$$(F \oplus G)(S) = F(S) \oplus G(S)$$).

But it’s still just the coproduct. The Cauchy product of linear species is defined by

$$(F \cdot G)(S) = \sum_{X \subseteq S} F(X) \otimes G(S - X)$$

We can also compose linear species! Everything is very similar. But now it’s connected to the representation theory of the symmetric group, because the category $\mathsf{E}$ is equivalent to the coproduct of all the 1-object categories $B S_n$ corresponding to the symmetric groups, and a functor from $B S_n$ to $\mathsf{Vect}$ is the same as a representation of $S_n$. And because representations of the symmetric group are classified by Young diagrams, so are linear species.

I won’t go into this more now, but my friends Joe and Todd and I have studied this subject in great detail, and it connects many areas of mathematics in a delightful way:

• John Baez, Joe Moeller and Todd Trimble, Schur functors and categorified plethysm.

• John Baez, Joe Moeller and Todd Trimble, 2-Rig extensions and the splitting principle.

For example, the second paper here relates linear species to the ring of symmetric functions, another popular and fundamental topic in combinatorics.