Basic structures
Generating functions
Proof techniques
Combinatorial identities
Polytopes
A (combinatorial) species is a presheaf or higher categorical presheaf on the groupoid core(FinSet), the permutation groupoid.
A species is a symmetric sequence by another name. Meaning: they are categorically equivalent notions.
The category of species, $Species := PSh(core(FinSet))$, is the category of presheaves on the groupoid $\mathbb{P} := core(FinSet)$ of finite sets and bijections, the core of FinSet:
For more, see structure type.
A 2-species (usually called a stuff type) is a 2-presheaf on core(FinSet), i.e. a pseudofunctor
to the 2-category Grpd.
Generally, an $\infty$-species or homotopical species is an (∞,1)-presheaf on $core(FinSet)$, i.e. an (∞,1)-functor
to the (∞,1)-category ∞Grpd (Gepner-Haugseng-Kock 17, Def. 3.2.9).
The (∞,1)-category of $\infty$-species is the (∞,1)-category of (∞,1)-presheaves
For more on this see also below the discussion In homotopy type theory.
There are in fact 5 important monoidal structures on the category of species.
The sum $A + B$ of two species $A$, $B$ is their coproduct $A \coprod B$. Since colimits of presheaves are computed objectwise, we have
The generating function of the sum of species is the sum of their generating functions.
The category $core(FinSet)$ becomes a monoidal category under disjoint union of finite sets. This monoidal structure $(core(FinSet), \coprod)$ induces canonically the Day convolution monoidal structure on $Species := PSh(core(FinSet))$. This is often called the Cauchy product of species, or sometimes (confusingly) just the “product”, since the generating function of the Cauchy product of species is the product of their generating functions.
Explicitly, the Cauchy product of species $A$ and $B$ is given by the coend
The category of species also has cartesian products. Since products of presheaves are computed objectwise, we have
This operation is often called the Hadamard product of species.
The category $core(FinSet)$ also becomes a monoidal category under cartesian product of finite sets. This monoidal structure induces another Day convolution monoidal structure on $Species := PSh(core(FinSet))$. This could be called the Dirichlet product of species, or sometimes simply the product, since the Dirichlet series of this product of species is the product of their Dirichlet series. (See Dirichlet series and the Hasse–Weil zeta function.)
Finally, there is a monoidal structure on the category of species known as plethysm or composition. The generating function of a composite of two species is the composite of their generating functions (in the sense of formal power series). A monoid with respect to the plethysm tensor product is called an operad.
The following discusses formalization of the concept of species in homotopy type theory.
Let FinSet be the type of finite sets (see at hSet). Notice that in homotopy type theory this automatically comes out as the groupoid of finite sets (see also at universe in type theory), so we may (and do) suppress writing “core” here.
A species is a type $X \colon Type$ equipped with a function into $FinSet$. Hence the type of all species is the dependent sum
of all function types $X \to FinSet$ as $X$ ranges over the type of types.
Write
for the unit of the 0-truncation modality on FinSet, going into the type of natural numbers.
Given a species $f \colon X \to FinSet$ as in def. , its “decategorification” is the composite
The generating function of a species $f \colon X \to FinSet$, def. , is
where $fib(-)$ denotes the homotopy fiber and $Fin(n)$ denotes a 0-type with exactly $n$ elements.
If $\Phi : FinSet \to Type$ is a family of types, then we obtain the species
with generating function
If $\Phi$ is a stuff, structure, or property on finite sets, then we immediately know something about its generating function, considered as an exponential generating function:
If $\Phi(A)$ is contractible for all $A$, then $\Phi(Fin(n)) = 1$, so its generating function is the exponential function $e^{z}$.
If $\Phi(A)$ is a family of mere propositions, then every coefficient is either $0$ or $1$, according to whether $A$ can be equipped with a $\Phi$-structure or not.
If $\Phi(A)$ is a family of sets (i.e., a structure type), then every coefficient is an element of the type of natural numbers $\mathbb{N}$.
If $\Phi(A)$ has a higher homotopy level (i.e., is a stuff type), then the coefficients are in $[0, \infty)$.
Since any species $f : X \to Type$ is equal to
every species is equal to one obtained from a stuff type.
The five monoidal structures mentioned above under Operations on species can be represented in HoTT, along with a couple other useful operations. We give four of the five monoidal structures here. For more operations, see (Dougherty15). We assume throughout this subsection that $f : X \to \Finset$ and $g : Y \to Finset$ are two species, and $\Phi, \Psi : FinSet \to Type$ are two stuff types.
The recursion principle for the coproduct gives the species
If $X$ and $Y$ are obtained from $\Phi$ and $\Psi$, respectively, then the coproduct is equal to
The generating function for the coproduct is
The Hadamard product of species is
which for stuff types is equal to
The generating functions are related by
where $X_{n}$ and $Y_{n}$ are the $n$th coefficients of the functions ${|X|}(z)$ and ${|Y|}(z)$, respectively.
The name “Hadamard product” is used in (Aguiar-Mahajan10) and (Bergeron-Labelle-Leroux08). In (Baez-Dolan01) ${|\langle X, Y \rangle|}(1)$ is called the “inner product” of stuff types, because equipping the category of stuff types with this operation makes it a categorified version of the Hilbert space of a quantum harmonic oscillator.
The Cauchy product of species is given by sending two species $f,g$ as in def. to the species given by
The Cauchy product, def. , is eqivalently the phased tensor product on the slice over the symmetric monoidal groupoid $(FinSet, \coprod)$.
For stuff types $\Phi$, $\Psi$, their Cauchy product, def. , is equal to
In this form the Cauchy product is discussed in (Aguiar-Mahajan 10, def. 8.5, Aguiar-Mahajan 12, section 2.2). Monoids and comonoid in the resulting monoidal category of species are discussed in (Aguiar-Mahajan 10, section 8.2) and Hopf monoids in this category in (Aguiar-Mahajan 12, section 2.2).
This means that $\Phi\Psi$ stuff on a finite set is the stuff of “being chopped in two, with $\Phi$ stuff on one part and $\Psi$ stuff on the other”.
The generating function is
The composition of two species is
where $\bigoplus_{i=1}^{n}g(P(i))$ is the $n$-ary direct sum of the finite sets $g(P(i))$. For stuff types, this amounts to
That is, $\Phi \tilde{\circ} \Psi$ stuff on a finite set is a partition of the set into $card(C)$ subsets, with $\Phi$ stuff on the partition and $\Psi$ stuff on each of the subsets.
The generating function of the composition is
This species is also called the plethysm product.
Under groupoid cardinality
every (tame) ∞-groupoid is mapped to a real number
A species $\mathbf{X}$ assigns an ∞-groupoid $\mathbf{X}_n$ to each natural number $n \in \mathbb{Z}$. Therefore under groupoid cardinality we may naturally think of a tame species as mapping to a power series
This cardinality operation maps the above addition and multiplication of combinatorial species to addition and multiplication of power series.
That coproduct of species maps to sum of their cardinalities is trivial. That Day convolution of species maps under cardinality to the product of their cardinality series depends a little bit more subtly on the combinatorial prefactors:
If in the definition of combinatorial species the domain core(FinSet) is replaced with FinVect and also the presheaves are take with values in FinVect then one obtains the notion of Schur functor.
Instead of $core(FinSet)$, we may choose as domain $\mathbf{B} A$ for a small category $A$, with objects $\langle a_i \rangle_{i \in I}$, for $I$ in $core(FinSet)$, i.e., finite families of objects of $A$. Also, instead of $Set$ valued presheaves, we may consider those valued in presheaves on a small category $B$. This joint generalisation yields what are called generalised species. These generalised species can be collected in a cartesian closed 2-category (FGHW).
The notion of species goes back to
An expositional discussion can be found at
See also wikipedia: combinatorial species and
François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire des structures arborescentes , LaCIM, Montréal (1994). English version: Combinatorial species and tree-like structures, Cambridge University Press (1998).
F. Bergeron, G. Labelle, P. Leroux, Introduction to the theory of species of structures, 2008, pdf
François Bergeron, Species and variations on the theme of species, invited talk at Category Theory and Computer Science ‘04, Copenhagen (2004). Slides (pdf).
G. Labelle, video intro into combinatorial species at Newton Institute, Cambridge 2008
Marcelo Aguiar, Swapneel Mahajan, Monoidal Functors, Species and Hopf Algebras, With forewords by Kenneth Brown, Stephen Chase, André Joyal. CRM Monograph Series 29 Amer. Math. Soc. 2010. lii+784 pp. (author pdf)
Marcelo Aguiar, Swapneel Mahajan, Hopf monoids in the category of species (arXiv:1210.3120)
An application in computer science:
Homotopical species are defined in (Def. 3.2.9):
Formalization in homotopy type theory:
Brent Yorgey, Combinatorial Species and labelled structures. (pdf)
John Dougherty, Species in HoTT (pdf) (formalization in Coq)
An application in statistical mechanics:
Discussion in relation to Feynman diagrams:
Discussion of generalised species:
Last revised on June 13, 2021 at 11:14:38. See the history of this page for a list of all contributions to it.