Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

June 26, 2025

Counting with Categories (Part 3)

Posted by John Baez

Here’s my third and final set of lecture notes for a 412\frac{1}{2}-hour minicourse at the Summer School on Algebra at the Zografou campus of the National Technical University of Athens.

Part 1 is here, and Part 2 is here.

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 [x]\mathbb{Z}[x] is the free commutative ring on one generator.

In fact it’s almost true that every species gives an element of [x]\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 [[x]]\mathbb{R}[[x]], a ring that’s a kind of ‘completion’ of [x]\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 [x]\mathbb{Z}[x] is the free commutative ring on one generator, the category of species Set E\mathsf{Set}^\mathsf{E} is the free symmetric 2-rig on one generator.

Substitution of species

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

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

sending xx to PP:

f(x)=P f(x) = P

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

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

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

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

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

sending XX to PP:

F(X)=P F(X) = P

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

F(Q)=QP 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 QQ and PP are species, to put a QPQ \circ P-structure on a finite set SS is to choose an unordered partition of SS into nonempty sets T 1,,T nT_1, \dots, T_n:

S=T 1T n,ijT iT j= S = T_1 \cup \cdots T_n , \qquad i \ne j \implies T_i \cap T_j = \emptyset

and put a PP-structure on {1,,n}\{1, \dots, n\} and a QQ-structure on each set T iT_i. Moreover

QP^=Q^P^ \widehat{Q \circ P} = \widehat{Q} \circ \widehat{P}

if the constant term of P^[[x]]\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\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 Exp\text{Exp} because its generating function is the power series for the exponential function:

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

Let X 22!\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

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

where

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

so

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

Now let’s compose these species, and let

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

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

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

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

and thus

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

so

n0|F(n)|n! = e x 2/2 = 1+(x 2/2)+(x 2/2) 22!+(x 2/2) 33!+ = k012 kk!x 2k \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=2kn = 2k is even,

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

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

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

But 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 nn-element set into nonempty parts? This is called the nnth Bell number, b nb_n. Let’s see if we can calculate it!

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

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

Exp\text{Exp} is our old friend ‘being a finite set’. NE\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 Exp\text{Exp}-structure on the set of parts, and put an NE\text{NE}-structure on each part. That gives the isomorphism above!

We know that

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

and similarly

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

Thus by the theorem,

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

So by the definition of the Bell numbers,

n0b nn!x n=e e x1 \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 x1e^{e^x - 1} only up to order x 3x^3:

e e x1 = exp(x+x 22+x 36+) = 1+(x+x 22+x 36+)+12(x+x 22+) 2+16x 3+ = 1+x+22!x 2+53!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,b 1=1,b 2=2,b 3=5 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:

Linear species

Finally, let me just conclude by mentioning a variant. We can define the category of linear species to be Vect E\mathsf{Vect}^\mathsf{E} where Vect\mathsf{Vect} is the category of complex vector spaces and linear maps. So, it’s just like the category of species but with Set\mathsf{Set} replaced by Vect\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:EVectF, G : \mathsf{E} \to \mathsf{Vect}, we define

(FG)(S)=F(S)G(S) (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

(FG)(S)= XSF(X)G(SX) (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 E\mathsf{E} is equivalent to the coproduct of all the 1-object categories BS nB S_n corresponding to the symmetric groups, and a functor from BS nB S_n to Vect\mathsf{Vect} is the same as a representation of S nS_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:

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

Posted at June 26, 2025 1:03 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3605

6 Comments & 1 Trackback

Read the post Counting with Categories (Part 1)
Weblog: The n-Category Café
Excerpt: First lecture in a 4.5-hour minicourse on combinatorics with species.
Tracked: June 27, 2025 9:12 AM

Re: Counting with Categories (Part 3)

james dolan should complain that you misspelled generatingfunctionology as Generatingfunctionology.

Say a species S has a generating function g, and g satisfies a linear differential equation p with polynomial coefficients, i.e. p(g)=0. (I think about D-modules from time to time.) For example, e^x is annihilated by p = 1 y’ - 1 y. Is there a nice categorification of “p(g)=0” that one can state directly about S?

Posted by: Allen Knutson on July 2, 2025 5:30 AM | Permalink

Re: Counting with Categories (Part 3)

When I first met James online on sci.math, he always typed in all caps. I eventually told him that made him look like a crank. He told me he’d think about that and maybe do something about it. A few days later he started writing in all lower case, and he has ever since. I think he mainly dislikes unnecessary fiddling with typography, finding it distracting.

Publications seem to differ on whether the book’s title really is generatingfunctionology, or whether that just happens to be the font of the title on the cover of the book (a subtle distinction).

The best way to write the differential equation obeyed by a species SS is not

P(S)=0 P(S) = 0

but

SQ(S) S \cong Q(S)

where QQ is some polynomial coefficient differential operator with Q[X,ddX]Q \in \mathbb{N}[X, \frac{d}{d X}]. This gives a recursive definition of the species SS, very much like the recursive definition I gave in Part 2 of the species of rooted labeled binary trees:

BX+B 2 B \cong X + B^2

Species obeying such recursive definitions tend to describe tree-like structures, and they’re studied extensively in this book:

  • François Bergeron, Gilbert Labelle and Pierre Leroux. Combinatorial Species and Tree-like Structures, Cambridge University Press, 1998.

though honestly I forget how far they go in relating properties of species to properties of the differential equations they obey. I am very interested in understanding the branch cut in the solutions to

BX+B 2 B \cong X + B^2

and how the theory of branched coverings of \mathbb{C} is related to species, but I haven’t gotten very far yet. Maybe I should try to categorify the theory of DD-modules, instead.

Posted by: John Baez on July 2, 2025 5:59 AM | Permalink

Re: Counting with Categories (Part 3)

Where does the tree-like structure story relate to Lagrange inversion, as in More secrets of the associahedra? Maybe I’m asking about categorifying that formula.

Also, is the Lagrange inversion formula about the formal group of Diff(S 1)Diff(S^1), and if so, does the tree-based (or associahedron-based) formula for the inverse have an extension to Virasoro? At which point I’d also want to know how to involve the formal Virasoro group in the Lazard ring story.

Posted by: Allen Knutson on July 2, 2025 3:23 PM | Permalink

Re: Counting with Categories (Part 3)

Good questions! I don’t really understand that formula for the compositional inverse of a formal power series in terms of associahedra… so before I could give any interesting answer, I’d have to think about that. I’ll just note that if we want to categorify this formula, we’ll need to handle formal power series with negative coefficients. The generating function for a species has only nonnegative coefficients. One way to get a formal power series with negative coefficients is from the generating function of a ‘derived species’ — e.g. a functor FF from the groupoid of finite sets not to FinSet\mathsf{FinSet} but to the category of bounded chain complexes of finite-dimensional vector spaces, with quasi-isomorphisms inverted. The idea is to use the Euler characteristic as a substitute for cardinality in defining the generating function:

F^= n0χ(F(n))n!x n \widehat{F} = \sum_{n \ge 0} \frac{\chi(F(n))}{n!} x^n

where F(n)F(n) is the chain complex that FF associates to the nn-element set.

(Lately I’ve been working on derived species with Todd Trimble, so they’re on my mind.)

Posted by: John Baez on July 2, 2025 3:31 PM | Permalink

Re: Counting with Categories (Part 3)

Looking a bit more at the paper we’re talking about

it’s clear that my Euler characteristic idea was on the right track, but the generating function idea was not.

I don’t understand most of what’s going on, but it’s fun to seek the key point at which counting faces in an associahedron becomes important for inverting formal power series. (Here I mean either inverting with respect to ordinary multiplication, or with respect to composition: the associahedron shows up for both!)

I think it’s Theorem 7.1, which gives a formula involving a sum over faces 𝔮\mathfrak{q} of the associahedron, weighted by (1) dim(𝔮)(-1)^{dim(\mathfrak{q})}. That’s already very reminiscent of an Euler characteristic, but in the proof they come out and say

We would like to interpret this as an Euler characteristic, but….

and then point out an obstacle, and then overcome this obstacle.

But they are not, as I’d guessed above, interpreting this sum in terms of the generating function of some derived species! Instead they are interpreting it as the antipode in a certain specific Hopf monoid in the category of “vector species”, i.e. the category of Vect\mathsf{Vect}-valued species, i.e. the category Vect E\mathsf{Vect}^{\mathsf{E}} where E\mathsf{E} is the groupoid of finite sets.

Since the antipode is a morphism in the category of vector species, rather than an object, this makes it much easier for it to involve minus signs. However, I don’t know why this morphism should be related to the associahedron, since I don’t yet understand the proof of Theorem 7.1.

Theorem 7.1 is proved using a simpler formula for the antipode, which they call “Takeuchi’s formula”—see Definition 2.11. This is a general formula giving any connected bimonoid HH in vector species an antipode, and thus making it a Hopf monoid.

(“Connected” here means that the vector space H()H(\emptyset) is the ground field. This should remind you of the definition of a connected \mathbb{N}-graded algebra.)

Posted by: John Baez on July 2, 2025 6:39 PM | Permalink

Re: Counting with Categories (Part 3)

John wrote:

it’s clear that my Euler characteristic idea was on the right track, but the generating function idea was not.

Or maybe it is… but it’s simply not the track Aguiar and Ardila followed. I’ve been working on your questions more with Todd Trimble, and the idea of categorifying Lagrange inversion is proving to be very interesting, but it will take a while for me to make enough clear progress to write back. I hope less than 14 years.

Posted by: John Baez on July 6, 2025 3:10 AM | Permalink