Editing Combinatorial species (section)

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