The n-Category Café

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. We’ll count them in a while.

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(S)| = 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 $X \subseteq S$ and put an $F$-structure on $X$ and a $G$-structure on $S - X$. 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}$ where an $\text{Exp}$-structure on a finite set is no extra structure at all. That is, 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.

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 $X \subset S$, which will be the set of fixed points of $f$, and to choose a derangement of $S - X$. 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}{6} + \frac{x^4}{24} - \cdots \right)(1 + x + x^2 + x^3 + x^4 + \cdots )$$

$$= \frac{1}{0!} + \frac{0}{1!} x + \frac{1}{2!}x^2 + \frac{2}{3!} x^3 + \frac{9}{4!} x^4 + \cdots$$

so we see that

$$D(0) = 1, \quad D(1) = 0, \quad D(2) = 1, \quad D(3) = 2, \quad D(4) = 9 , \dots$$

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

• Homework: Let’s get deranged!

Also, you’ll notice that I wrote

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

without ever defining an isomorphism of species! So you can try to figure out what that should mean, and I’ll say more about it next time.