A course on combinatorial species

Combinatorial species provide a categorical foundation for enumerative combinatorics. Nowadays they find application in combinatorics, algebra and logic (where they provide an axiomatisation for the notion of algebraic theory à la Lawvere), algebraic topology (where they provide a foundation for the theory of operads), computer science (containers, etc.) and many other areas of pure Mathematics.

Combinatorial species are a true mathematical gem; they elegantly tie together a disparate variety of objects naturally arising in everyday mathematical practice.

Combinatorial species were invented by A. Joyal.

After that, entire books have been written on the topic: among these, we will often refer to two

  1. The red book: Bergeron, François, et al. Combinatorial species and tree-like structures. No. 67. Cambridge University Press, 1998.
  2. The big book: Aguiar, Marcelo, and Swapneel Arvind Mahajan. Monoidal functors, species and Hopf algebras. Vol. 29. Providence, RI: American Mathematical Society, 2010.

(Yes, I will refer them as “red” and “big” in the following).

This website is the logbook of a reading seminar that I would like to start at taltech during Fall 2021. Its focus is not on rigor or completeness. Its style is idiosyncratic. Its purpose is to collect pointers to the -quite vast- literature on species (while tickling my nitpickery). My hope is not to drop the project midway (hysterical-laughter.mp3).

Preliminaries; finite sets, convolution

The category $\bf Fin$ has objects the finite sets and morphisms all functions; a skeleton of $\bf Fin$ is the category whose objects are sets $[n]={1,\dots,n}$ for $n\ge 0$ (with the convention that $[0]=\varnothing$), and morphisms are functions $f : [n] \to [m]$.

The category P and species

The fundamental object of study of the theory of combinatorial species is the category $\bf P$ of finite sets and bijections, and its presheaf category $[{\bf P}^\text{op}, {\bf Set}]$. (Note: since a groupoid is a self-dual category, there is not much difference between $[{\bf P}^\text{op}, {\bf Set}]$ and $[{\bf P}, {\bf Set}]$, but we will usually speak about the second category.)

Monoidal Structures on P

A fundamental tenet of categorical combinatorics is that the richness of the objects it tries to study (“combinatorial objects”, broadly intended) comes from the synergy between many different structures one can equip the categories meant to describe said combinatorial objects.

Some explicit combinatorial identities

We have seen that to a combinatorial species we can associate at least two important invariants “quantities”, i.e. two formal power series from which we can deduce properties of the species. If $|X_n|$ denotes the cardinality of a set, and $F : {\bf P} \to {\bf Set}$ is a combinatorial species,

Species and analytic functors

This chapter embarks on a more category-theoretic study of species. Every species has a canonical decomposition as an infinite sum $f_0 + f_1 + f_2 + \dots$ and it gives rise to an endofunctor $\bar F $ of $\bf Set$ that admits a “Taylor expansion”. Such functors are called analytic, and they can be characterised intrinsically as the finitary endofunctors of $\bf Set$ satisfying a weak exactness property.

A theorem on trees

Cayley, Arthur. “A theorem on trees.” Quart. J. Math. 23 (1889): 376-378.

An application of species to functional programming

One of the many ways of formally describing a programming language is via denotational semantics, in which a term $T$ of type $\tau$ is represented by a mathematical object $\llbracket T \rrbracket \in \llbracket\tau\rrbracket$ (its denotation), where $\llbracket\tau\rrbracket$ is a domain, a certain kind of structured set. Terms of type $\sigma\to\tau$ are then interpreted as suitable functions $\llbracket\sigma\rrbracket\to\llbracket\tau\rrbracket$ between domains.1