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. One goal of species theory is to be able to analyse complicated structures by describing them in terms of transformations and combinations of simpler structures. These operations correspond to equivalent manipulations of generating functions, so producing such functions for complicated structures is much easier than with other methods. The theory was introduced, carefully elaborated and applied by Canadian researchers around André Joyal.
The power of the theory comes from its level of abstraction. The "description format" of a structure (such as adjacency list versus adjacency matrix for graphs) is irrelevant, because species are purely algebraic. Category theory provides a useful language for the concepts that arise here, but it is not necessary to understand categories before being able to work with species.
The category of species is equivalent to the category of symmetric sequences in finite sets.
Definition of species
Any species consists of individual combinatorial structures built on the elements of some finite set: for example, a combinatorial graph is a structure of edges among a given set of vertices, and the species of graphs includes all graphs on all finite sets. Furthermore, a member of a species can have its underying set relabeled by the elements of any other equinumerous set, for example relabeling the vertices of a graph gives "the same graph structure" on the new vertices, i.e. an isomorphic graph.
This leads to the formal definition of a combinatorial species. Let be the category of finite sets, with the morphisms of the category being the bijections between these sets. A species is a functor
For each finite set A in , the finite set F[A] is called the set of F-structures on A, or the set of structures of species F on A. Further, by the definition of a functor, if φ is a bijection between sets A and B, then F[φ] is a bijection between the sets of F-structures F[A] and F[B], called transport of F-structures along φ.
For example, the "species of permutations" maps each finite set A to the set S[A] of all permutations of A (all ways of ordering A into a list), and each bijection f from A to another set B naturally induces a bijection (a relabeling) taking each permutation of A to a corresponding permutation of B, namely a bijection . Similarly, the "species of partitions" can be defined by assigning to each finite set the set of all its partitions, and the "power set species" assigns to each finite set its power set. 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.
Two finite sets are in bijection whenever they have the same cardinality (number of elements); thus by definition the corresponding species sets are also in bijection, and the (finite) cardinality of depends only on the cardinality of A. In particular, the exponential generating series F(x) of a species F can be defined:
where is the cardinality of for any set A having n elements; e.g., .
Some examples: writing , The species of sets (traditionally called E, from the French "ensemble", meaning "set") is the functor which maps A to { A}. Then , so . The species S of permutations, described above, has . . The species T2 of ordered pairs (2-tuples) is the functor taking a set A to A2. Then and .
Calculus of species
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. Species with the same generating function might not be isomorphic, but isomorphic species do always have the same generating function.