Editing Combinatorial species

{{more footnotes|date=June 2018}}
In [[combinatorics|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 proof|bijective proofs]] involving them.  Examples of combinatorial species are ([[wiktionary:finite|finite]]) [[Graph (discrete mathematics)|graphs]], [[permutation]]s, [[Tree (graph theory)|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 sequence]]s in finite sets.<ref>{{nlab|id=symmetric+sequence|title=Symmetric sequence}}</ref>

==Definition of species==
[[File:Combinatorial species generic structure.svg|thumb|Schematic illustration of a combinatorial species structure on five elements by using a Labelle diagram]]

Any species consists of individual combinatorial structures built on the elements of some finite set: for example, a [[Graph (discrete mathematics)|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 [[Isomorphism|isomorphic]] graph.

This leads to the formal definition of a ''combinatorial species''. Let <math>\mathcal{B}</math> be the [[category (mathematics)|category]] of [[finite set]]s, with the [[morphism]]s of the category being the [[bijection]]s between these sets. A ''species'' is a [[functor]]<ref>{{harvnb|Joyal|1981|loc=§ 1.1. Definition 1.}}</ref>

:<math>F\colon \mathcal{B} \to \mathcal{B}. </math>

For each finite set ''A'' in <math>\mathcal{B}</math>, the finite set ''F''[''A'']<ref group=note>Joyal prefers to write <math>F[A]</math> for <math>F(A)</math>, the value of ''F'' at ''A''.</ref> 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 φ''.<ref name=lasa-invi>Federico G. Lastaria, [http://math.unipa.it/~grim/ELastaria221-230.PDF An invitation to Combinatorial Species]. (2002)</ref>

For example, the "species of permutations"<ref>{{harvnb|Joyal|1981|loc=§ 1.1. Example 3.}}</ref> 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 <math>S[f]:S[A]\to S[B]</math>. Similarly, the "species of partitions" can be defined by assigning to each finite set the set of all its [[partition of a set|partition]]s, 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 <math>F[A]</math> depends only on the cardinality of ''A''.<ref group=note>If <math>u : A \to B</math> is a bijection, then <math>F[u]: F[A] \to F[B]</math> is a bijection and thus <math>F[A], F[B]</math> have the same cardinality.</ref> In particular, the ''[[exponential generating series]]'' ''F''(''x'') of a species ''F'' can be defined:<ref>{{harvnb|Joyal|1981|loc=§ 1.1.1.}}</ref>
:<math>F(x) = \sum_{n \ge 0} \operatorname{Card} F[n] \frac{x^n}{n!}</math>
where <math>\operatorname{Card} F[n]</math> is the cardinality of <math>F[A]</math> for any set ''A'' having ''n'' elements; e.g., <math>A = \{ 1, 2, \dots, n \}</math>.

Some examples: writing <math>f_n = \operatorname{Card} F[n]</math>,
* The species of sets (traditionally called ''E'', from the French "''ensemble''", meaning "set") is the functor which maps ''A'' to {''A''}. Then <math>f_n = 1</math>, so <math>E(x) = e^x</math>.
* The species ''S'' of [[permutation]]s, described above, has <math>f_n = n!</math>. <math>S(x) = 1/(1 - x)</math>. 
* The species ''T''<sub>2</sub> of ordered pairs (2-[[tuple]]s) is the functor taking a set ''A'' to ''A''<sup>2</sup>. Then <math>f_n = n^2</math> and <math>T_2(x) = x (x+1) e^x</math>.

==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.

=== Addition ===
'''Addition''' of species is defined by the [[disjoint union]] of sets, and corresponds to a choice between structures.<ref>{{harvnb|Joyal|1981|loc=§ 2.1.}}</ref> For species ''F'' and ''G'', define (''F'' + ''G'')[''A''] to be the disjoint union (also written "+") of ''F''[''A''] and ''G''[''A'']. It follows that (''F''&nbsp;+&nbsp;''G'')(''x'') =&nbsp;''F''(''x'')&nbsp;+&nbsp;''G''(''x''). As a demonstration, take ''E''<sup>+</sup> to be the species of non-empty sets, whose generating function is ''E''<sup>+</sup>(''x'')&nbsp;=&nbsp;''e''<sup>''x''</sup>&nbsp;−&nbsp;1, and '''1''' the species of the [[empty set]], whose generating function is '''1'''(''x'') = 1. It follows that the sum of the two species ''E''&nbsp;=&nbsp;'''1'''&nbsp;+&nbsp;''E''<sup>+</sup>: in words, "a set is either empty or non-empty". Equations like this can be read as referring to a single structure, as well as to the entire collection of structures.

===Multiplication ===
'''Multiplying''' species is slightly more complicated. It is possible to just take the Cartesian product of sets as the definition, but the combinatorial interpretation of this is not quite right. (See below for the use of this kind of product.) Rather than putting together two unrelated structures on the same set, the [[multiplication operator]] uses the idea of splitting the set into two components, constructing an ''F''-structure on one and a ''G''-structure on the other.<ref>{{harvnb|Joyal|1981|loc=§ 2.1. Definition 5}}</ref>
:<math>(F \cdot G)[A] = \sum_{A=B+C} F[B] \times G[C].</math>
This is a disjoint union over all possible binary partitions of&nbsp;''A''. It is straightforward to show that multiplication is [[Associativity|associative]] and [[Commutativity|commutative]] ([[up to]] [[isomorphism]]), and [[Distributivity|distributive]] over addition. As for the generating series, (''F''&nbsp;·&nbsp;''G'')(''x'')&nbsp;=&nbsp;''F''(''x'')''G''(''x'').

The diagram below shows one possible (''F''&nbsp;·&nbsp;''G'')-structure on a set with five elements. The ''F''-structure (red) picks up three elements of the base set, and the ''G''-structure (light blue) takes the rest. Other structures will have ''F'' and ''G'' splitting the set in a different way. The set (''F''&nbsp;·&nbsp;''G'')[''A''], where ''A'' is the base set, is the disjoint union of all such structures.

[[File:Multiplication of combinatorial species.svg|200px|center]]

The addition and multiplication of species are the most comprehensive expression of the sum and product rules of counting.{{Citation needed|reason=In what sense are they "the most comprehensive"? is there a citation with more context?|date=July 2024}}

===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]].

===Differentiation===
'''[[derivative|Differentiation]]''' of species intuitively corresponds to building "structures with a hole", as shown in the illustration below.

[[File:Derivative of combinatorial species.svg|200px|center]]

Formally,<ref>{{harvnb|Joyal|1981|loc=§ 2.3. Definition 8}}</ref>

:<math>(F')[A] = F[A \uplus \{\star\}],</math>

where <math>\star</math> is some distinguished new element not present in <math>A</math>.

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'']&nbsp;=&nbsp;''F''[''A''&nbsp;+&nbsp;{*}], where {*} is a singleton set and "+" is disjoint union. The more advanced parts of the theory of species use differentiation extensively, to construct and solve [[differential equation]]s on species and series. 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&mdash;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'''&nbsp;=&nbsp;''L''·''L''. The exponential generating function of ''L'' is ''L''(''x'')&nbsp;=&nbsp;1/(1&nbsp;−&nbsp;''x''), and indeed:

:<math>
  \frac d {dx} {(1-x)}^{-1} = {(1-x)}^{-2}.
</math>

The generalized differentiation formulas are to be found in a previous research by N. G. de Bruijn, published in 1964.

The species ''C'' of cyclic permutations takes a set ''A'' to the set of all cycles on ''A''. Removing a single element from a cycle reduces it to a list: ''C'''&nbsp;=&nbsp;''L''. We can [[Integral|integrate]] the generating function of ''L'' to produce that for&nbsp;''C''.

:<math>
  C(x) = 1 + \int_0^x \frac{dt}{1-t} = 1 + \log \frac{1}{1-x}.
</math>

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.

===Further operations===
There are a variety of other manipulations which may be performed on species. These are necessary to express more complicated structures, such as [[directed graph]]s or [[bigraph]]s.

'''Pointing''' selects a single element in a structure.<ref>{{cite book |last1=Flajolet |first1=Philippe |author-link1=Philippe Flajolet |last2=Sedgewick |first2=Robert |author-link2=Robert Sedgewick (computer scientist) |date=2009 |title=Analytic combinatorics}}</ref> Given a species ''F'', the corresponding pointed species ''F''<sup>•</sup> is defined by ''F''<sup>•</sup>[''A''] = ''A'' &times; ''F''[''A'']. Thus each ''F''<sup>•</sup>-structure is an ''F''-structure with one element distinguished. Pointing is related to [[differentiation (mathematics)|differentiation]] by the relation ''F''<sup>•</sup> = ''X''·''F' '', so ''F''<sup>•</sup>(''x'') = ''x'' ''F' ''(''x''). The species of [[pointed set]]s, ''E''<sup>•</sup>, is particularly important as a building block for many of the more complex constructions.

The '''Cartesian product''' of two species{{citation needed|date=December 2018}} is a species which can build two structures on the same set at the same time. It is different from the ordinary multiplication operator in that all elements of the base set are shared between the two structures. An (''F'' &times; ''G'')-structure can be seen as a superposition of an ''F''-structure and a ''G''-structure. 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. The generating function (''F'' &times; ''G'')(''x'') is the Hadamard or coefficient-wise product of ''F''(''x'') and ''G''(''x'').

The species ''E''<sup>•</sup> &times; ''E''<sup>•</sup> can be seen as making two independent selections from the base set. The two points might coincide, unlike in ''X''·''X''·''E'', where they are forced to be different.

As functors, species ''F'' and ''G'' may be combined by '''functorial composition''':{{citation needed|date=December 2018}} <math>(F \,\Box\, G) [A] = F[G[A] ]</math> (the box symbol is used, because the circle is already in use for substitution). This constructs an ''F''-structure on the set of all ''G''-structures on the set ''A''. For example, if ''F'' is the functor taking a set to its power set, a structure of the composed species is some subset of the ''G''-structures on ''A''. If we now take ''G'' to be ''E''<sup>•</sup> &times; ''E''<sup>•</sup> from above, we obtain the species of directed graphs, with self-loops permitted. (A directed graph is a set of edges, and edges are pairs of nodes: so a graph is a subset of the set of pairs of elements of the node set ''A''.) Other families of graphs, as well as many other structures, can be defined in this way.

==Software==
Operations with species are supported by [[SageMath]]<ref>Sage documentation on [http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/species/species.html combinatorial species].</ref> and, using a special package, also by [[Haskell (programming language)|Haskell]].<ref>Haskell package [http://hackage.haskell.org/package/species species].</ref><ref>{{Cite book | first = Yorgey | last = Brent A. | chapter = Species and functors and types, oh my! | publisher = ACM | year = 2010 | isbn = 978-1-4503-0252-4 | pages = 147–158 | doi = 10.1145/1863523.1863542| title = Proceedings of the third ACM Haskell symposium on Haskell - Haskell '10 | citeseerx = 10.1.1.165.6421 | s2cid = 511418 }}</ref>

== Variants ==
* A species ''in k sorts'' is a functor <math>\mathcal{B}^k \rightarrow \mathcal{B}</math>. Here, the structures produced can have elements drawn from distinct sources.{{citation needed|date=December 2018}}
* A functor to <math>\mathcal{B}_R</math>, the category of ''R''-weighted sets for ''R'' a [[Ring (mathematics)|ring]] of [[power series]], is a ''weighted species''.{{citation needed|date=December 2018}}

If “finite sets with bijections” is replaced with “finite vector spaces with linear transformations”, then one gets the notion of [[polynomial functor]] (after imposing some finiteness condition).{{citation needed|date=December 2018}}

==See also==
* [[Container (type theory)]]

==Notes==
{{reflist|group=note}}
{{Reflist}}

==References==
* {{cite journal 
| last1=Joyal | first1=André | authorlink1=André Joyal
| date=October 1981
| title=Une théorie combinatoire des séries formelles
| journal=[[Advances in Mathematics]]
| volume=42
| issue=1
| pages=1–82
| doi=10.1016/0001-8708(81)90052-9 | doi-access=}}
* Bruijn, de, N. G. (1964). Pólya's theory of counting. In E. F. Beckenbach (Ed.), Applied combinatorical mathematics (pp. 144-184)
* Labelle, Jacques. ''Quelques espèces sur les ensembles de petite cardinalité.'', Ann. Sc. Math. Québec 9.1 (1985): 31-58.
*{{cite journal
| last1=Labelle | first1=J.
| last2=Yeh | first2=Y. N.
| title=The Relation Between Burnside Rings and Combinatorial Species
| journal=[[Journal of Combinatorial Theory]] | series=Series A
| volume=50
| issue=2
| date=1989
| pages=269–284
| doi=10.1016/0097-3165(89)90019-8 | doi-access=free}}
* Yves Chiricota, ''Classification des espèces moléculaires de degré 6 et 7'',  Ann. Sci. Math. Québec 17 (1993), no. 1, 11–37.
* François Bergeron, Gilbert Labelle, Pierre Leroux, ''Théorie des espèces et combinatoire des structures arborescentes'', LaCIM, Montréal (1994). English version: [http://bergeron.math.uqam.ca/Species/especes.html ''Combinatorial Species and Tree-like Structures''] {{Webarchive|url=https://web.archive.org/web/20061002194205/http://bergeron.math.uqam.ca/Species/especes.html |date=2006-10-02 }}, Cambridge University Press (1998).
* Kerber, Adalbert (1999), Applied [[finite group]] actions, Algorithms and Combinatorics, 19 (2nd ed.), Berlin, New York: [[Springer Science+Business Media|Springer-Verlag]], {{ISBN|978-3-540-65941-9}}, MR 1716962, OCLC 247593131

==External links==
* {{MathWorld|Species|Species}}
* {{nlab|id=species|title=species}}

[[Category:Enumerative combinatorics]]
[[Category:Algebraic combinatorics]]