Editing Combinatorial species (section)

===Composition===
'''Composition''', also called substitution, is more complicated again. The basic idea is to replace components of ''F'' with ''G''-structures, forming (''F''&nbsp;∘&nbsp;''G'').<ref>{{harvnb|Joyal|1981|loc=§ 2.2. Definition 7}}</ref> 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 formal definition is:

:<math>(F \circ G)[A] = \sum_{\pi \in P[A]} (F[\pi] \times \prod_{B \in \pi} G[B]).</math>

Here, ''P'' is the species of partitions, so ''P''[''A''] is the set of all partitions of ''A''. This definition says that an element of (''F''&nbsp;∘&nbsp;''G'')[''A''] is made up of an ''F''-structure on some partition of ''A'', and a ''G''-structure on each component of the partition. The generating series is <math>(F \circ G)(x) = F(G(x))</math>.

One such structure is shown below. Three ''G''-structures (light blue) divide up the five-element base set between them; then, an ''F''-structure (red) is built to connect the ''G''-structures.

[[File:Composition (substitution) of combinatorial species.svg|200px|center]]

These last two operations may be illustrated by the example of trees. First, define ''X'' to be the species "singleton" whose generating series is ''X''(''x'')&nbsp;=&nbsp;''x''. Then the species ''Ar'' of rooted trees (from the French "''arborescence''") is defined recursively by ''Ar''&nbsp;=&nbsp;''X''&nbsp;·&nbsp;''E''(''Ar''). This equation says that a tree consists of a single root and a set of (sub-)trees. The recursion does ''not'' need an explicit base case: it only generates trees in the context of being applied to some finite set. One way to think about this is that the ''Ar'' functor is being applied repeatedly to a "supply" of elements from the set &mdash; each time, one element is taken by ''X'', and the others distributed by ''E'' among the ''Ar'' subtrees, until there are no more elements to give to ''E''. This shows that algebraic descriptions of species are quite different from type specifications in programming languages like [[Haskell (programming language)|Haskell]].

Likewise, the species ''P'' can be characterised as ''P''&nbsp;=&nbsp;''E''(''E''<sup>+</sup>): "a partition is a pairwise disjoint set of nonempty sets (using up all the elements of the input set)". The exponential generating series for ''P'' is <math>P(x) = e^{(e^x - 1)}</math>, which is the series for the [[Bell numbers]].