Combinatorial species

In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for deriving the generating functions of discrete structures, which allows one to not merely count these structures but give bijective proofs involving them.

Examples of combinatorial species are (finite) graphs, permutations, trees, and so on; each of these has an associated generating function which counts how many structures there are of a certain size.

The theory was introduced, carefully elaborated and applied by Canadian researchers around André Joyal.

The adjacent diagram shows a structure (represented by a red dot) built on a set of five distinct elements (represented by blue dots); a corresponding structure could be built out of any five elements.

, Arithmetic on generating functions corresponds to certain "natural" operations on species.

The basic operations are addition, multiplication, composition, and differentiation; it is also necessary to define equality on species.

Category theory already has a way of describing when two functors are equivalent: a natural isomorphism.

In this context, it just means that for each A there is a bijection between F-structures on A and G-structures on A, which is "well-behaved" in its interaction with transport.

Addition of species is defined by the disjoint union of sets, and corresponds to a choice between structures.

It is possible to just take the Cartesian product of sets as the definition, but the combinatorial interpretation of this is not quite right.

It is straightforward to show that multiplication is associative and commutative (up to isomorphism), and distributive over addition.

The F-structure (red) picks up three elements of the base set, and the G-structure (light blue) takes the rest.

The addition and multiplication of species are the most comprehensive expression of the sum and product rules of counting.

[8] As with multiplication, this is done by splitting the input set A; the disjoint subsets are given to G to make G-structures, and the set of subsets is given to F, to make the F-structure linking the G-structures.

It is required for G to map the empty set to itself, in order for composition to work.

The recursion does not need an explicit base case: it only generates trees in the context of being applied to some finite set.

Differentiation of species intuitively corresponds to building "structures with a hole", as shown in the illustration below.

To differentiate the associated exponential series, the sequence of coefficients needs to be shifted one place to the "left" (losing the first term).

This suggests a definition for species: F' [A] = F[A + {*}], where {*} is a singleton set and "+" is disjoint union.

The idea of adding (or removing) a single part of a structure is a powerful one: it can be used to establish relationships between seemingly unconnected species.

For example, consider a structure of the species L of linear orders—lists of elements of the ground set.

Removing an element of a list splits it into two parts (possibly empty); in symbols, this is L' = L·L.

The exponential generating function of L is L(x) = 1/(1 − x), and indeed: The generalized differentiation formulas are to be found in a previous research by N. G. de Bruijn, published in 1964.

Removing a single element from a cycle reduces it to a list: C' = L. We can integrate the generating function of L to produce that for C. A nice example of integration of a species is the completion of a line (coordinatizated by a field) with the infinite point and obtaining a projective line.

The species of pointed sets, E•, is particularly important as a building block for many of the more complex constructions.

It is different from the ordinary multiplication operator in that all elements of the base set are shared between the two structures.

Bigraphs could be described as the superposition of a graph and a set of trees: each node of the bigraph is part of a graph, and at the same time part of some tree that describes how nodes are nested.

As functors, species F and G may be combined by functorial composition:[citation needed]

If we now take G to be E• × E• from above, we obtain the species of directed graphs, with self-loops permitted.

Operations with species are supported by SageMath[11] and, using a special package, also by Haskell.