Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: mathematics

Topic: power series and associahedra

John Baez (Jul 03 2025 at 06:29):

I'm trying to understand a startling connection between the inverse of a formal power series (with respect to composition) and associahedra:

https://mathstodon.xyz/@johncarlosbaez/114787573420344878

I'm starting to feel the core idea is rather simple, though I can't quite put my finger on it yet.

John Baez (Jul 04 2025 at 13:07):

(deleted)

Madeleine Birchfield (Jul 04 2025 at 13:27):

There are some issues with the LaTeX of the last two formulae.

For the first formula, the $$n^\overline{k}$$ doesn't work on Zulip for some reason. Instead, one needs to enclose the superscript in curly brackets in LaTeX, like $n^{\overline{k}}$

Madeleine Birchfield (Jul 04 2025 at 13:33):

For the second, I think you can only use double $ symbols if the math LaTeX is on a single line. Otherwise you have to use the math code block, like

$$\begin{align} \hat{f}_k &= \frac{f_{k+1}}{(k+1)f_{1}}, \\ g_1 &= \frac{1}{f_{1}}, \text{ and} \\ n^{\overline{k}} &= n(n+1)\cdots (n+k-1) \end{align}$$

or enclose each of the three lines with a pair of double $ symbols and remove the & symbols, like

$\hat{f}_k = \frac{f_{k+1}}{(k+1)f_{1}},$
$g_1 = \frac{1}{f_{1}}, \text{ and}$
$n^{\overline{k}} = n(n+1)\cdots (n+k-1)$

John Baez (Jul 04 2025 at 13:39):

Yes, thanks. I had to go to my gate in the airport - that's why I left the LaTeX unfixed.

John Baez (Jul 04 2025 at 13:42):

Ardila and Aguiar's formula for the inverse of a formal power series involves associahedra. An older formula uses Bell polynomials. Suppose

$\displaystyle{ f(w) = \sum_{k=1}^\infty f_k \frac{w^k}{k!} }$

normalized with $f_1 = 1$ to make things simple, and suppose

$\displaystyle{ g(z) = \sum_{k=1}^\infty g_k \frac{z^k}{k!} }$

is the inverse of $f$ with respect to (formal) composition:

$f(g(z)) = z$

Then $g_1 = 1$, and the Lagrange inversion formula says that for $n \ge 2$ we have

$\displaystyle{ g_n = \sum_{k=1}^{n-1} (-1)^k n^{\overline{k}} B_{n-1,k}(\hat{f}_1,\hat{f}_2,\ldots,\hat{f}_{n-k}) }$

where

$\displaystyle{ \hat{f}_k = \frac{f_{k+1}}{(k+1)} }$

and the rising powers $n^{\overline{k}}$ are defined by

$\displaystyle{ n^{\overline{k}} = n(n+1)\cdots (n+k-1) }$

while $B_{n-1,k}$ are the Bell polynomials.

All these things deserve to be categorified, but for now let me just explain the Bell polynomials to myself.

John Baez (Jul 04 2025 at 13:48):

It seems easiest to explain them with an example. $B_{n,k}$ is a polynomial in $n-1$ variables, which depends on $0 \le k \le n$. It's related to how you can partition an $n$-element set into $k$ (nonempty) blocks. For example:

$B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5x_1+15x_4x_2+10x_3^2$

This says that if we partition a 6-element set into 2 blocks there are:

• 6 ways to partition it into a block of size 5 and a block of size 1
• 15 ways to partition it into a block of size 4 and a block of size 2
• 10 ways to partition it into two blocks of size 3.

and that's all the ways.

John Baez (Jul 04 2025 at 13:50):

So, if you know all the Bell polynomials, you know how to partition any finite set into some chosen number of blocks of some chosen sizes.

John Baez (Jul 04 2025 at 13:52):

As a result, the Bell numbers contain more information than the Stirling numbers of the second kind,

$\lbrace{ n \atop k }\rbrace$

which says how many ways there are to partition an $n$-element set into $k$ blocks.

John Baez (Jul 05 2025 at 08:48):

Let me start by categorifying some basic stuff about Stirling numbers of the second kind. I said $\lbrace{ n \atop k }\rbrace$ is the number of ways to partition an $n$-element set into $k$ blocks. (By the way, a partition of a set is a collection of disjoint nonempty subsets called blocks whose union is the whole set.)

A more categorical way to put it is that $\lbrace{ n \atop k }\rbrace$ counts epis $n \twoheadrightarrow k$ up to isomorphism of the codomain. We could call these quotient sets of the set $n$. This is dual to how monos $k \rightarrowtail n$ up to isomorphisms of the domain are called subsets of $n$.

So, there are $\binom{n}{k}$ $k$-element subsets of $n$, and dually $\lbrace{ n \atop k }\rbrace$ $k$-element quotient sets of $n$.

John Baez (Jul 05 2025 at 08:51):

We have

$\displaystyle{ \sum_{k = 0}^n \binom{n}{k} = 2^n}$

and this formula is also true at the categorified level:

$\displaystyle{ \sum_{k = 0}^{|S|} \binom{S}{k} \cong 2^S}$

when $\binom{S}{k}$ is the set of $k$-element subsets of the finite set $S$ and $2^S$ is the power set of $S$.

John Baez (Jul 05 2025 at 08:54):

Dually we have

$\displaystyle{ \sum_{k = 0}^n \left\lbrace{ n \atop k }\right\rbrace = B_n}$

where $n$ is the $n$ th Bell number, meaning the number of quotient sets of $n$, or partitions of $n$. This too easily categorifies:

$\displaystyle{ \sum_{k = 0}^{|S|} \left\lbrace{ S \atop k }\right\rbrace \cong B_S}$

where now $\lbrace{S \atop k }\rbrace$ is the set of $k$-element quotient sets of $S$ and $B_S$ is the set of quotient sets of $S$.

John Baez (Jul 05 2025 at 09:02):

The binomial coefficient $\binom{n}{k}$ counts monos $k \rightarrowtail n$ up to isomorphism of the domain $k$. However, we might simply want to count monos $k \rightarrowtail n$, with none of this "up to isomorphism" baloney. The number of these is clearly the falling power

$n^{\underline{k}} = n(n-1)(n-2) \cdots (n - k + 1)$

When we count these monos up to isomorphism of the domain $k$ we get

$\displaystyle{ \frac{n^{\underline{k}}}{k!} = \frac{ n(n-1)(n-2) \cdots (n - k + 1) }{k!} = \binom{n}{k} }$

John Baez (Jul 05 2025 at 09:12):

Similarly, while $\lbrace{ n \atop k }\rbrace$ counts epis $n \twoheadrightarrow k$ up to isomorphism of the codomain, we might want to just count such epis pure and simple. I don't know a name for the answer, but the problem here is not that we don't have enough names for things: it's more like we have too many! Whatever it's called, it's just $\lbrace{ n \atop k }\rbrace$ times $k!$.

John Baez (Jul 05 2025 at 09:18):

Now for something fun. Every function $f: n \to i$ has an epi-mono factorization, unique up to isomorphism:

$f \twoheadrightarrow\text{im}(f) \rightarrowtail k$

Since there $i^n$ functions $f: n \to i$, we get a cool identity:

$\displaystyle{ i^n = \sum_{k = 0}^n \left\lbrace{ n \atop k }\right\rbrace i^{\underline{k}} }$

John Baez (Jul 05 2025 at 09:22):

Puzzle - why are we using $\left\lbrace{ n \atop k }\right\rbrace$ here, which counts epis up to isomorphism of the codomain, while we're using $i^{\underline{k}}$, which counts monos... not monos up to isomorphism of the domain?

John Baez (Jul 05 2025 at 09:24):

Anyway, this identity painlessly categorifies because it was derived by thinking about the category of finite sets. If $S$ and $T$ are finite sets we have

$\displaystyle{ S^T \cong \sum_{k = 0}^{|T|} \left\lbrace{ T \atop k }\right\rbrace S^{\underline{k}} }$

I don't want to think about infinite sets now, but you can think about how all this stuff generalizes to those if you want. Presumably we simply let $k$ range over all cardinals and define $\left\lbrace{ T \atop k }\right\rbrace$ to be the empty set if there are no epis from $T$ to $k$, and define $S^{\underline{k}}$ to be empty if there are no monos from $k$ to $S$.

But actually, if you're going to generalize this basic combinatorics to possibly infinite sets, you might as well generalize it to a large class of categories for which the relevant principles, like uniqueness of epi-mono factorizations, actually make sense.

[EDIT: I tried doing that later.]

Simon Burton (Jul 05 2025 at 09:38):

(i think you switched the epi-mono arrow decorations above...)

John Baez (Jul 05 2025 at 11:08):

Thanks! You left it as exercise to locate all the places where I did it. :woozy_face: I fixed it in one location.

John Baez (Jul 05 2025 at 11:14):

Let me just say a bit about generalizing the identity

$\displaystyle{ i^n = \sum_{k = 0}^n \left\lbrace{ n \atop k }\right\rbrace i^{\underline{k}} }$

to other categories. Suppose we have any category with existence and uniqueness-up-to-isomorphism of epi-mono factorizations. Choose a skeleton of this category, say $C$. For any objects $i,k,n \in C$ let

• $\text{epi}(n,k)$ be the set of epis from $n$ to $k$

and let

• $\text{mon}(k,i)$ be the set of monos from $k$ to $n$.

The group of automorphisms $\text{aut}(k)$ acts on the right on the former set, and on the left on the latter. Then I believe we have (nonconstructively)

$\displaystyle{ \text{hom}(n,i) \cong \sum_{k \in C} \text{epi}(n,k) \times_{\text{aut}(k)} \text{mon}(k,i) }$

if this is wrong someone please correct me!

If I'm on the right track, there's probably a constructively valid approach that avoids using a skeleton which replaces the sum by a coend. I believe the coend breaks up into a sum over isomorphism classes of objects if we use the axiom of choice, and I wanted to do that to make the formula look more like the usual version for the category of finite sets:

$\displaystyle{ i^n = \sum_{k = 0}^n \left\lbrace{ n \atop k }\right\rbrace i^{\underline{k}} }$

In the case of finite sets the division by $\text{aut}(k)$ is hidden in the notation, since

$\displaystyle{ \left\lbrace{ n \atop k }\right\rbrace = |\text{epi}(n,k) / \text{aut}(k)| }$

and because $\text{aut}(k)$ acts freely on $\text{epi}(n,k)$ (which is a general fact!) we have

$|\text{epi}(n,k) / \text{aut}(k)| = |\text{epi}(n,k)| / |\text{aut}(k)|$

John Baez (Jul 05 2025 at 11:35):

Anyway, I wanted to talk about generating functions! It's well-known, and explained in my lecture notes, that the number of partitions of an $n$-element set, $B_n$, obeys

$\displaystyle{ \sum_{n = 0}^\infty \frac{B_n}{n!} = e^{e^x - 1} }$

Indeed I show that this is a decategorified version of the fact that

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

where the three species here are:

• $\text{Part}$: the species of "being a finite set equipped with a partition", which has generating function

$\displaystyle{ \widehat{\text{Part}} = \sum_{n = 0}^\infty \frac{B_n}{n!} }$

• $\text{Exp}$: the structure of "being a finite set", which has generating function

$\displaystyle{ \widehat{\text{Exp}} = \sum_{n = 0}^\infty \frac{1}{n!} = e^x }$

• $\text{NE}$: the structure of "being a nonempty finite set", which has generating function

$\displaystyle{ \widehat{\text{NE}} = \sum_{n = 1}^\infty \frac{1}{n!} = e^x - 1 }$

John Baez (Jul 05 2025 at 11:52):

Like I said, all this is well known - it's in any good book on generating functions or species. But there's something that's at least $\varepsilon$ less well known. We can write

$\displaystyle{ e^{e^x - 1} = \sum_{n = 0}^\infty \frac{B_n}{n!} x^n = \sum_{n = 0}^\infty \sum_{k = 0}^n \frac{\left\lbrace{ n \atop k }\right\rbrace}{n!} x^n }$

since every partition of $n$ is a partition into $k$ parts for some $k$:

$\displaystyle{ B_n = \sum_{k = 0}^n \left\lbrace{ n \atop k }\right\rbrace }$

Since

$\displaystyle{ \left\lbrace{ n \atop k }\right\rbrace = |\text{epi}(n,k) / \text{aut}(k)| = \frac{\text{epi}(n,k)}{k!} }$

we get

$\displaystyle{ e^{e^x - 1} = \sum_{n = 0}^\infty \sum_{k = 0}^\infty \frac{\text{epi}(n,k)}{n!k!} x^n }$

John Baez (Jul 05 2025 at 11:58):

Here I've harmlessly increased the range of summation to $0 \le k \le \infty$ since there are no epis from $n$ to $k$ when $k > n$.

Now, this quantity

$\displaystyle{ \sum_{n = 0}^\infty \sum_{k = 0}^\infty \frac{\text{epi}(n,k)}{n!k!} x^n }$

is really the two-variable power series

$\displaystyle{ \sum_{n = 0}^\infty \sum_{k = 0}^\infty \frac{\text{epi}(n,k)}{n!k!} x^n y^k }$

evaluated at $y = 1$, and this two-variable power series is the generating function of a "two-variable species", i.e. a structure you can put on pairs of finite sets. This two-variable species is just $\text{epi}$, where $\text{epi}(n,k)$ is the set of epimorphisms from $n$ to $k$. (The awkward contravariance in one argument can be eliminated because a two-variable species is a functor from the groupoid of finite sets squared to $\mathsf{Set}$.)

John Baez (Jul 05 2025 at 12:01):

In other words, the generating function of $\text{epi}$ is

$\widehat{\text{epi}} = \displaystyle{ \sum_{n = 0}^\infty \sum_{k = 0}^\infty \frac{\text{epi}(n,k)}{n!k!} x^n y^k }$

$\displaystyle{ = \sum_{n = 0}^\infty \sum_{k = 0}^\infty \frac{1}{n!} \left\lbrace{ n \atop k }\right\rbrace x^n y^k }$

John Baez (Jul 05 2025 at 12:05):

But what does this equal, in closed form? All I've said is that at $y = 1$ it equals $e^{e^x - 1}$.

David Egolf (Jul 05 2025 at 16:05):

This is fun! Thanks for sharing these ideas!

John Baez said:

Now for something fun. Every function $f: n \to i$ has an epi-mono factorization, unique up to isomorphism:

$f \twoheadrightarrow\text{im}(f) \rightarrowtail k$

Since there $i^n$ functions $f: n \to i$, we get a cool identity:

$\displaystyle{ i^n = \sum_{k = 0}^n \left\lbrace{ n \atop k }\right\rbrace i^{\underline{k}} }$

This was confusing me a little bit. Could you maybe elaborate on what $i$ is here? Is it perhaps some arbitrary subset of $k$? (I notice that the image of $f$ has to admit a monomorphism to $k$).

David Egolf (Jul 05 2025 at 16:30):

(Also - I really love the idea that binomial coefficients are "dual" to Stirling numbers!)

John Baez (Jul 05 2025 at 16:37):

Sorry, I explained some things in my lecture notes which I did not mention here. In set theory natural numbers are often defined recursively:

$0 = \emptyset, \qquad i = \{0, \dots, i-1\}$

This lets us use $i$ to mean both 1) the natural number $i$ and 2) a particular set with $i$ elements. They're the same thing!

I'm using $i, n, k$ in this way in most of my calculations above. This greases the wheels of categorification.

If we also work in a skeleton of $\mathsf{FinSet}$, then every finite set is equal to $i$ for some natural number $i$. This is also somewhat convenient, so I often do this. If we don't, then every finite set is isomorphic to $i$ for some $i$, and we have to say things a bit more long-windedly, but nothing important changes.

David Egolf (Jul 05 2025 at 16:45):

Thanks for clarifying!

It still seems to me we need some relationship between $i$ and $k$ for this to work:

John Baez said:

Now for something fun. Every function $f: n \to i$ has an epi-mono factorization, unique up to isomorphism:

$f \twoheadrightarrow\text{im}(f) \rightarrowtail k$

Since there $i^n$ functions $f: n \to i$, we get a cool identity:

$\displaystyle{ i^n = \sum_{k = 0}^n \left\lbrace{ n \atop k }\right\rbrace i^{\underline{k}} }$

For example, if $i$ has more elements than $k$, then I don't see how to produce an epi-mono factorization for a surjective $f:n \to i$ of the form indicated.

David Egolf (Jul 05 2025 at 16:50):

(I would have expected the epi-mono factorization of $f:n \to i$ to look like this: $n \twoheadrightarrow\text{im}(f) \rightarrowtail i$. But instead we have $k$ getting involved!)

John Baez (Jul 05 2025 at 16:50):

You mean $n \twoheadrightarrow\text{im}(f) \rightarrowtail i$.

$\text{im}(f)$ must have some cardinality, so in a skeleton of $\mathsf{FinSet}$ it must equal $k$ for some $k$. That's why I'm summing over $k$.

John Baez (Jul 05 2025 at 16:53):

Does that make sense? You seem to also have another question, about what happens when $k$ gets "too big".

David Egolf (Jul 05 2025 at 16:53):

Oh ok! It wasn't clear to me that $k$ was just $\mathrm{im}(f)$ up to isomorphism. I thought we were allowing it to vary more freely.

That explains things. Thanks!

John Baez (Jul 05 2025 at 16:55):

In my formula I'm considering all possible functions from $n$ to $i$. There are $i^n$ of them. They all have epi-mono factorizations, and the epi-mono factorization is inevitably equal to (in a skeleton of $\mathsf{FinSet}$), or at least isomorphic to, one of the form

$n \twoheadrightarrow k \rightarrowtail i$

for some $k$.

David Egolf (Jul 05 2025 at 17:00):

John Baez said:

Puzzle - why are we using $\left\lbrace{ n \atop k }\right\rbrace$ here, which counts epis up to isomorphism of the codomain, while we're using $i^{\underline{k}}$, which counts monos... not monos up to isomorphism of the domain?

I suppose using $\left\lbrace{ n \atop k }\right\rbrace$ intuitively means we are counting our functions using their images. Then, given a particular image, there's a whole bunch of ways to get a specific function - and $i^{\underline{k}}$ counts those.

David Egolf (Jul 05 2025 at 17:01):

If we just multiplied (number of epimorphisms $:n \to k$)(number of monomorphisms $:k \to i$) I guess we'd overestimate the number of distinct functions $:n \to i$.

David Egolf (Jul 05 2025 at 17:05):

Hmm, I might be confused - some of my last two messages might be wrong.

I probably want to meditate on what $\left\lbrace{ n \atop k }\right\rbrace$ means.

EDIT:
I think I understand now why we need this factor of $1/k!$. To illustrate in an example in case someone else finds it helpful:

We would like to have a term in our sum for the case where $k$ has three elements. This counts the number of functions $:n \to i$ that have an image with three elements. The epimorphism part of our factorization determines which elements in $n$ get mapped to the same value by $f$. But each map $:n \to k$ that induces the same partition of $n$ will specify the same information. So we need to divide out by these "shufflings" of $k$.

John Baez (Jul 05 2025 at 17:07):

I said what it means, but it's probably better to figure it out yourself.

If we just multiplied (number of epimorphisms $:n \to k$)(number of monomorphisms $:k \to i$) I guess we'd overestimate the number of distinct functions $:n \to i$.

Yes! That's why the formula

$\displaystyle{ i^n = \sum_{k = 0}^n \left\lbrace{ n \atop k }\right\rbrace i^{\underline{k}} }$

multiplies the number of monomorphisms from $k$ to $i$,

$\displaystyle{ i^{\underline{k}} }$

by the number of epimorphisms from $n$ to $k$ modulo automorphisms of $k$,

$\left\lbrace{ n \atop k }\right\rbrace$

which is $1/k!$ times the number of epimorphisms from $n$ to $k$.

It was completely arbitrary that I packed the necessary division by $k!$ into the epi part rather than the mono part. The only reason is that I don't know a slick name for the number of epis from $n$ to $k$: it's

$k! \left\lbrace{ n \atop k }\right\rbrace$

John Baez (Jul 05 2025 at 17:11):

At some point above I wrote a more symmetrical, conceptual formula which applies whenever we have a category with epi-mono factorizations that are unique up to isomorphism:

$\displaystyle{ \text{hom}(n,i) \cong \sum_k \text{epi}(n,k) \times_{\text{aut}(k)} \text{mon}(k,i) }$

where we sum over all objects $k$ in a skeleton. The weird $\times$ with a subscript is a standard notation for

$\displaystyle{ \text{hom}(n,i) \cong \sum_k \frac{\text{epi}(n,k) \times \text{mon}(k,i)}{{\text{aut}(k)}} }$

where we mod out by the action of the group $\text{aut}(k)$, which acts on both $\text{epi}(n,k)$ and $\text{mon}(k,i)$. This should remind you of stuff when you were composing profunctors! It's really a coend.

David Egolf (Jul 05 2025 at 17:17):

Very cool stuff! And that does seem reminiscent of profunctor composition!

John Baez (Jul 05 2025 at 17:18):

It probably is a special case of profunctor composition.

John Baez (Jul 06 2025 at 10:53):

Here's a way to think of epi-mono factorizations in the category of finite sets in terms of profunctor composition.

Let $\mathsf{E}$ be the groupoid of finite sets and bijections, and let

$\text{epi} : \text{E}^{\text{op}} \times \text{E} \to \mathsf{Set}$

be the obvious functor such that $\text{epi}(S,T)$ is the set of epimorphisms from $S$ to $T$. I say "obvious" functor because you can precompose or postcompose an onto function with a bijection and get an onto function.

Let

$\text{mon} : \text{E}^{\text{op}} \times \text{E} \to \mathsf{Set}$

be the same thing but with monmorphisms, and let

$\text{fun} : \text{E}^{\text{op}} \times \text{E} \to \mathsf{Set}$

be the same thing but with all functions. Note that $\text{fun}$ is not $\text{hom}$ in the groupoid of finite sets and bijections.

We can think of $\text{epi}, \text{mon}$ and $\text{fun}$ as profunctors from $\mathsf{E}$ to itself, and if we use composition of profunctors we get

$\text{mon} \circ \text{epi} \cong \text{fun}$

because any function is a composite of an epi and a mono in a manner that's unique up to isomorphism. In other words we have a coend formula

$\displaystyle{ \text{fun}(X,Z) \cong \int^{Z \in \mathsf{E}} \text{epi}(X,Y) \times \text{mon}(Y,Z) }$

John Baez (Jul 06 2025 at 10:59):

We can express the coend as a coproduct over isomorphism classes of objects since groupoids have no morphisms between nonisomorphic objects. If we take a skeleton of $\mathsf{E}$ whose objects are ordinals $k = \{0, \dots, k-1\}$, one for each isomorphism class of finite set, this gives:

$\displaystyle{ \text{hom}(n,i) \cong \sum_{k=0}^\infty \frac{\text{epi}(n,k) \times \text{mon}(k,i)}{{\text{aut}(k)}} }$

Then, if we take cardinalities, we get our old friend

$\displaystyle{ i^n = \sum_{k = 0}^n \left\lbrace{ n \atop k }\right\rbrace i^{\underline{k}} }$

Okay, I think I've beaten this horse dead by now!

John Baez (Jul 06 2025 at 11:08):

All this stuff is a bit of a digression. What I wanted to do is figure out the 2-variable generating function for epimorphisms, which is defined to be

$\displaystyle{ \widehat{\text{epi}}(x,y) = \sum_{n \ge 0} \sum_{k \ge 0} \frac{|\text{epi}(n,k)|}{n! k!} x^n y^k }$

John Baez (Jul 06 2025 at 11:10):

This is just a convenient way of encoding all the numbers

$\displaystyle{ \left\lbrace{ n \atop k }\right\rbrace := |\text{epi}(n,k)| }$

into a power series, which can then manipulated in various ways to extract interesting information.

It is also fun to build a 2-variable generating functino for $\text{mon}$, and of course it's fun to also do $\text{fun}$, but I have some special interest in epimorphisms right now, in part because the numbers $|\text{epi}(n,k)|$, called Stirling numbers of the second kind, are less familiar to me than the numbers

$|\text{mon}(n,k)| = k(k-1) \cdots (k-n+1)$

called falling powers, or the even simpler numbers

$|\text{fun}(n,k)| = k^n$

which are ordinary powers.

This is probably connected to David Ellerman's point that isomorphism classes of epis in $\mathsf{Set}$, called partitions, are dual to isomorphism classes of monos, called subsets, yet the logic of subsets is much more widely studied than the logic of partitions. So, we all study binomial coefficients more than Stirling numbers of the second kind.

John Baez (Jul 06 2025 at 11:35):

Anyway, here goes.

If we fix $k$, $\text{epi}(-,k)$ sends any set to the set of ways of partitioning it into $k$ (nonempty disjoint) subsets. Thus it's a composite of species:

$\displaystyle{ \text{epi}(-,k) \cong \frac{X^k}{k!} \circ \text{NE} }$

where, as explained in my lecture notes:

• $X^k/k!$ is the species 'being a $k$-element set' with generating function $x^k/k!$.
• $\text{NE}$ is the species 'being a nonempty finite set', with generating function $\exp(x) - 1$.

Thus the generating function of $\text{epi}(-,k)$ is the composite function

$\displaystyle{ \frac{(\exp(x) - 1)^k}{k!} }$

John Baez (Jul 06 2025 at 11:42):

In short, the generating function of $\text{epi}(-,k)$ is

$\displaystyle{ \widehat{ \text{epi}(-,k)} := \sum_{n \ge 0} \frac{|\text{epi}(n,k)|}{n!} x^n = \frac{(\exp(x) - 1)^k}{k!} }$

John Baez (Jul 06 2025 at 11:51):

Thus the 2-variable generating function for $\text{epi}$ is

$\displaystyle{ \widehat{\text{epi}} = \sum_{k \ge 0} \sum_{n\ge 0} \frac{|\text{epi}(n,k)|}{n! k!} x^n y^k}$

$\displaystyle{ = \sum_{k \ge 0} \frac{ (\exp(x) - 1)^k}{k!} y^k }$

$\displaystyle{ = e^{(e^x - 1)y} }$

It was tiring to typeset this, which is why I should be writing a book rather than individual posts, but the result is quite simple, with a bit of an exotic twist to it.

From this we can easily recover the usual generating functions for the Bell numbers $B_n$ (which count all partitions of an $n$-element set) and the Stirling numbers of the second kind, as well as things like Dobinski's formula, which says that the $n$ th Bell number is

$\displaystyle{ B_n = \frac{1}{e} \sum_{k \ge 0} \frac{k^n}{n!} }$

This is cool because it expresses an integer in terms of a formula involving a sum times $1/e$, and the sum looks like someone took the usual Taylor series for an exponential and got confused about it.