Combinatorial species

Combinatorial species are presheaves (or equivalently copresheaves) on the category of finite sets and bijections. Species were invented by Joyal as a categorification of generating functions in enumerative combinatorics.

Literature

Books

  • Bergeron, Labelle, Leroux, 1998: Combinatorial species and tree-like structures (doi)
  • Bergeron, Labelle, Leroux, 2008: Introduction to the theory of species of structures (pdf)
  • Aguiar & Mahajan, 2010: Monoidal functors, species and Hopf algebras (doi, pdf)

Applications to computer science

There are connections between combinatorial species, algebraic data types, and polynomial functors.

  • Kock, 2012: Data types with symmetries and polynomial functors over groupoids (doi, arxiv)
  • Yorgey, 2014, PhD thesis: Combinatorial species and labelled structures (pdf)
    • Yorgey, 2010: Species and functors and types, oh my! (doi, pdf)
    • Yorgey, Weirich, Carette, 2014, unpublished draft: Labelled structures and combinatorial species (pdf)

Restriction species

Restriction species, introduced by William Schmitt, are presheaves on the category of finite sets and injections. Because every injection factors as a bijection followed by an inclusion, a restriction species can be seen as an ordinary species equipped with a functorial family of restriction maps.

  • Schmitt, 1993: Hopf algebras of combinatorial species (doi)
  • Aguiar & Mahajan, 2010, Section 8.7.8: Species with restrictions and linearized comonoids
  • Yorgey, 2014, PhD thesis, Section 5.3: Partial species
  • Gálvez-Carrillo, Kock, Tonks, 2020: Decomposition spaces and restriction species (doi, arxiv)