Combinatorics, Lecture 2 (1 Oct 2019)

In Lecture 1, we gave the idea of what a species is and saw a few examples. Now we’ll explore the idea more and see more examples. We’ll also talk about the connection to generating functions, and some operations that let us build new species from old.

Thanks to Tim Hosgood for helping me out with both pictures and typing!

Generating functions

There’s a category of species and there’s a set of generating functions. Just like F and $\mathbb N$ , we’ll see how generating functions are a decategorification of species.

Let 0 denote the empty set, 1 denote the set {0}, 2 = {0,1}, etc. In general, for $n\in\mathbb{N}$ , let n denote {0, 1, … , n-1}. We can define all natural numbers this way. Representing the natural numbers this way is referred to as the von Neumann ordinals.

We use Set to denote the category of sets and functions, F to denote the category of finite sets and functions, and S to denote the category of finite sets and bijections.

Definition: A species is a functor $G \colon \mathsf S \to \mathsf{Set}$ . A finite species is a functor $G \colon \mathsf S \to \mathsf F$ .

We can turn a finite set X into a number: its cardinality |X|. This is useful because $X \cong Y$ in Set if and only if |X| = |Y|. What can we do that is like this for species? Given a species, we can cook up something called its generating function.

Let $\mathbb R[[x]]$ be the set of formal power series, which are expressions of the form

$\sum_{n\geq 0} a_n x^n$ with $a_n \in \mathbb R$ .

Note: we don’t care about convergence of these series at all.

You can add and multiply these, and they obey the axioms of a commutative ring. Note: the polynomial ring $\mathbb R[x]$ is a subring of $\mathbb R[[x]]$ .

Definition: Given a finite species $G \colon S \to F$ , its generating function is the formal power series |G| given by

$|G|(x) = \sum_{n \geq 0} \frac{|G(n)|}{n!} x^n$ .

Example: Let $C_k$ be the species of k-colorings of sets:

$C_k(X)$ = {ways to color the set X with k colors} = $k^X$ .

Let’s figure out what the generating function $|C_k|$ is:

$|C_k|(x) = \sum_{n\geq0} \frac{|C_k(n)|}{n!} x^n$
= $\sum_{n\geq0} \frac{|k^n|}{n!} x^n$
= $\sum_{n\geq0} \frac{k^n}{n!} x^n$
= $\sum_{n\geq0} \frac{(kx)^n}{n!}$
= $e^{kx}$ .

Example: Let $A_k$ be the species that says “there is exactly one $A_k$ -structure on an n-element set if n=k, and no structures otherwise.” That is, $A_k(X)$ is 1 if |X|=k, and 0 otherwise. This structure is really just a property, but we can still calculate its generating function:

$|A_k|(X) = \sum_{n\geq0} \frac{|A_k(n)|}{n!} x^n$
= $\frac{x^k}{k!}$ .

We can call $A_k$ the species of being a k-element set.

Operations on Species

Let’s figure out how to add and multiply species, since already know how to add and multiply power series. Given finite species G and H, we want these operations on species to match up with the corresponding operations on formal power series in the following way:

|G+H| = |G|+|H| and |GH| = |G||H|.

Addition of Species

Definition: Given two finite species $G,H \colon \mathsf S \to \mathsf{Set}$ , let $G+H \colon \mathsf S \to \mathsf{Set}$ be given by

(G+H)(X) = G(X)+H(X)

for a finite set X, and the obvious thing on bijections.

Theorem: |G+H|=|G|+|H|.

proof:

$|G+H|(x) = \sum_{n\geq0} \frac{|(G+H)(n)|}{n!} x^n$
= $\sum_{n\geq0} \frac{|G(n)+H(n)|}{n!} x^n$
= $\sum_{n\geq0} \frac{|G(n)|+|H(n)|}{n!} x^n$
= $\sum_{n\geq0} \frac{|G(n)|}{n!}x^n+\frac{|H(n)|}{n!} x^n$
= $\sum_{n\geq0} \frac{|G(n)|}{n!} x^n + \sum_{n\geq0} \frac{|H(n)|}{n!} x^n$
= $|G|(X) + |H|(X)$ .

Putting a (G+H)-structure on a finite set is the same as either putting a G-structure on it or putting an H-structure on it.

Example: $|C_1+C_2| = |C_1|+|C_2| = e^x+e^{2x}$ .

Multiplication

What about GH? Note that this multiplication we’re going to talk about does not correspond to putting a G-structure and an H-structure on X. In fact, if it did, then it turns out we wouldn’t get |GH| = |G||H|. So let’s work backwards from this property!

$|G|(x)|H|(x) = \left(\sum_{j\geq0} \frac{|G(j)|}{j!} x^j \right) \left( \sum_{k\geq0} \frac{|H(k)|}{k!} x^k \right)$
= $\sum_{j\geq0} \sum_{k\geq0} \frac{|G(j)||H(k)|}{j!k!} x^{j+k}$

then we cleverly substitute n=j+k to get

= $\sum_{n\geq0}\sum_{j=0}^n \frac{|G(j)| |H(n-j)|}{j!(n-j)!} x^n$
= $\sum_{n\geq0} \sum_{j=0}^n \frac{|G(j) \times H(n-j)|}{n!} \frac{n!}{j!(n-j)!} x^n$
= $\sum_{n\geq0} \left( \sum_{j=0}^n \binom{n}{j} |G(j) \times H(n-j)| \right) \frac{x^n}{n!}$

and so we want to define GH so that $|GH|(n) = \sum_{j=0}^n \binom{n}{j} |G(j) \times H(n-j)|$ . Define GH to be the species whose structure comes from chopping X into two disjoint parts, putting a G-structure on the first part, and putting an H-structure on the second part.

$GH(X) = \sum_{Y \subseteq X} G(Y) \times H(X-Y)$

Example: A $C_1C_2$ -structure on a set X is where we chop X into two parts, then 1-color the first part, and then 2-color the second part. This is the same as just 3-coloring X, as we can show: