nLab
species

Contents

Idea

A (combinatorial) species is a presheaf or higher categorical presheaf on the groupoid core(FinSet).

Definition

1-categorical

The category of species, Species:=PSh(core(FinSet))Species := PSh(core(FinSet)), is the category of presheaves on the groupoid :=core(FinSet)\mathbb{P} := core(FinSet) of finite sets and bijections, the core of FinSet:

^:=PSh(core(FinSet)). \hat \mathbb{P} := PSh(core(FinSet)) \,.

For more, see structure type.

2-categorical

A 2-species (usually called a stuff type) is a 2-presheaf on core(FinSet), i.e. a pseudofunctor

core(FinSet)Grpd core(FinSet) \to Grpd

to the 2-category Grpd.

(,1)(\infty,1)-categorical

Generally, an \infty-species or homotopical species is an (∞,1)-presheaf on core(FinSet)core(FinSet), i.e. an (∞,1)-functor

core(FinSet) opGrpd core(FinSet)^{op} \to \infty Grpd

to the (∞,1)-category ∞Grpd.

The (∞,1)-category of \infty-species is the (∞,1)-category of (∞,1)-presheaves

Species:=PSh (,1)(core(FinSet)), \infty Species := PSh_{(\infty,1)}(core(FinSet)) \,,

Operations on species

There are in fact 5 important monoidal structures on the category of species. For a discussion of all five, you’ll currently have to read about Schur functors, where these operations are discussed in the context of FinVectFin\Vect-valued species, i.e. FinVectFin\Vect-valued presheaves on the groupoid of finite sets. But here are two:

Sum

The sum A+BA + B of two species AA, BB is their coproduct ABA \coprod B. Since colimits of presheaves are computed objectwise, we have

(A+B) nA nB n. (A + B)_n \simeq A_n \coprod B_n \,.

Product

The category core(FinSet)core(FinSet) becomes a monoidal category under disjoint union of finite sets. This monoidal structure (core(FinSet),)(core(FinSet), \coprod) induces canonically the Day convolution monoidal structure on Species:=PSh(core(FinSet))Species := PSh(core(FinSet)).

For AA and BB two combinatorial species, their product is given by the coend

(AB) n nFinSetA k×B l×Hom core(FinSet)(n,k+l) k+l=n (k+l)!k!+l!(A k×B l). (A \otimes B)_n \simeq \int^{n \in FinSet} A_k \times B_l \times Hom_{core(FinSet)}(n,k+l) \simeq \coprod_{k+l = n} \prod_{\frac{(k+l)!}{k! + l!}} (A_k \times B_l) \,.

Cardinality

Under groupoid cardinality

:Grpd tame {|-|} : \infty Grpd_{tame} \to \mathbb{R}

every (tame) ∞-groupoid is mapped to a real number

XX:= [x]π 0(X) i=1 (π i(X,x) (1) i). X \mapsto {|X|} := \sum_{[x] \in \pi_0(X)}\prod_{i = 1}^{\infty} (\pi_i(X,x)^{(-1)^{i}}) \,.

A species X\mathbf{X} assigns an ∞-groupoid X n\mathbf{X}_n to each natural number nn \in \mathbb{Z}. Therefore under groupoid cardinality we may naturally think of a tame species as mapping to a power series

XX:= n=0 1n!X nz n[[z]]. \mathbf{X} \mapsto {|\mathbf{X}|} := \sum_{n = 0}^{\infty} \frac{1}{n!} {|\mathbf{X}_n|} z^n \in \mathbb{R}[ [ z ] ] \,.

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:

AB=AB= n=0 1n! k+l=nn!k!l!A kB l. {| A \otimes B |} = {|A|} \cdot {|B|} = \sum_{n=0}^\infty \frac{1}{n!} \sum_{k+l = n} \frac{n!}{k! l!} {|A_k|} \cdot {|B_l|} \,.

Variants

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.

References

The notion of species goes back to

An expositional discussion can be found at

  • Todd Trimble, Exponential Generating Function and Introduction to Species (blog) (scroll down a bit).

See also wikipedia: combinatorial species and

An application in computer science:

  • Brent Yorgey, Random testing and beyond! with combinatorial species, slides pdf; Species and functors and types, oh my, article, pdf

An application in statistical mechanics:

  • W. Faris, Combinatorial species and cluster expansions, Mosc. Math. J. 10:4 (2010), 713–727 pdf, MR2791054

Revised on September 19, 2012 11:38:58 by Urs Schreiber (82.169.65.155)