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 , 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 , 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 . A **finite species** is a functor .

We can turn a finite set X into a number: its cardinality |X|. This is useful because 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 be the set of **formal power series**, which are expressions of the form

with .

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 is a subring of .

**Definition**: Given a finite species , its **generating function** is the formal power series |G| given by

.

**Example**: Let be the species of k-colorings of sets:

= {ways to color the set X with k colors} = .

Let’s figure out what the generating function is:

=

=

=

= .

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

= .

We can call 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 , let 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:

=

=

=

=

= .

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**: .

### 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!

=

then we cleverly substitute n=j+k to get

=

=

=

and so we want to define GH so that . 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.

**Example**: A -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:

= =

= = .

Note that is *isomorphic*, but *not* equal, to .

## Next Time

In Lecture 3, we’ll talk about the *category* of species.

## 2 thoughts on “Combinatorics, Lecture 2 (1 Oct 2019)”