Since their introduction by Joyal [1] in 1981, combinatorial species have been exploited in a manifold of ways. Originally, they were conceived as a categorification of powerseries by Joyal: a combinatorial species is a collection of sets, one for each natural numbers, whose cardinalities make up the coefficients of a powerseries. In this way, one can think about powerseries in a richer context, and deduce enumerative results in very elegant ways. For example, Joyal provides in [1] a very short and celebrated proof of Cayley’s theorem that the number of labelled trees on vertices is .

Let us now introduce the objects of our interest formally.

In simple terms, a (*combinatorial) species *is a sequence of sets , each one with an action of the corresponding symmetric group . In particular, and are really just sets. If is another species, a *morphism of species from to *is a collection of equivariant functions . In this way, there is a *category of species, *which is simply a direct product of the various categories of -sets.

Because it will prove quite useful in upcoming discussions, we will think of a combinatorial species as *functor * from the category of finite sets and bijections, which we denote , to the category of sets, . Thus, to each finite set we will assign another set , which we call the -structures on , and to each bijection we will assign a bijection . We usually say that (each element of) is given a structure of species by means of , and think of as a rule of relabelling -structures, and if , we say is obtained by *transporting along . *Naturally, morphisms are now natural transformations. We will denote this category by .

To connect our two definitions of species, we observe that a skeleton of consists of the finite sets for a natural number, whose automorphism groups are precisely the symmetric groups . Thus every species is determined, up to isomorphism, by the sets and their respective -actions —this is exactly our simpler description of species.

Combinatorial species are a useful way of packing up our informal notion of a “collection of labelled combinatorial structures of kind” and how such structures are “relabelled”. Moreover, as we noted before, species project themselves onto powerseries, in the following concrete way. If is a combinatorial species, we define its *cardinality* to be the (formal) powerseries where is the cardinality of . The cardinality of only stores what its name alludes to: the cardinals of the various sets that determine , but it does not remember, for example, the action of the various symmetrics groups. Later on we will see more refined assignments that do this, at least partially.

To illustrate, there is a species of *linear orders *that assigns to every finite set the collection of bijections where . We think of as a word , and we assign to every bijection the map obtained by postcomposition with . This effectively just relabels a linear order on to one in according to . The reader should convince him or herself that, once we identify with in the obvious way, the action of on is the regular action of the symmetric group on itself. It is immediate that .

There is a similar species to , the species of *bijections, *that assigns to every finite set its collection of bijections, and assigns a bijection the map obtained by conjugating by . Once again, . However, one should note that and are not *isomorphic *species: the action of on is not isomorphic to that of on , since one action is the regular one, yet the other is by conjugation, and the orbits of the actions are not equinumerous.

This motivates us to assign to every species another species that remembers the automorphisms of each -structure. Concretely, let denote the species that assigns to each finite set the collection of pairs where and is a bijection on such that —this is called an *automorphism of . *The reader should ellucidate the way bijections should act on such pairs.

Let us now find the cardinality of . The cardinal of is the sum of the cardinals of the set of fixed points of as runs through , and by Burnside’s lemma, this is exactly , where is the cardinal of the orbit space of . Thus . One now observes at once that and differ, and we can conclude —once again— that such species are not isomorphic.

One can endow the category of species with a coproduct and a product, simply by using the coproduct and product of sets. Concretely, if and are species, their *sum *is the species that assigns to a finite set the set , and where bijections act in the obvious manner. Similarly, the *Hadamard product * assigns to a finite set the set and, again, is acted upon by bijections in the obvious way. Is is clear that the cardinality of a sum of species is the sum of their cardinalities —we will not concern ourselves, however, with the Hadamard product of powerseries.

There is yet a third operation one can perform on species that acts as the usual formal multiplication of powerseries, the *Cauchy product,* which is central to essentially all the modern algebraic treatment of species we will consider. The Cauchy product of two species assigns to a finite set the set , the sum running through all pairs of subsets of that are disjoint and whose union is : we call this a *decomposition of into two blocks,* and denote this situation by . The reader can imagine what a *decomposition of into blocks* is. If is a bijection and is a decomposition, there are induced bijections and which collect to form a bijection .

It is worth to remark than a structure of type is exactly a pair where and are “complementary” -and -structures, respectively. It is precisely this interpretation that motivates our definition. If is an integer, we will denote the product of with itself times by . The reader should note that we can identify with the collection decompositions of into blocks, where each block is given a structure of species . This is the same as a function where each fibre is given a structure of species .

As our notation suggests, the Cauchy product is a tensor product on , that is bilinear with respect to addition of species, so this category is monoidal (with an obvious symmetry that interchanges factors) and bicartesian. Moreover, there is the so desired equality that . Let us prove this:

The coefficient of in is , while the cardinality of is that of the union of as runs through subsets of . Now each of these sets has cardinality if has elements, and being the case there are of such -subsets of , we deduce this number is , as expected. Of course, the Cauchy product is so constructed for this to happen!

The advantages of having enriched the category in such a way that our cardinality map respects both products and is additive is that we can now perform combinatorial arguments in that give useful identities in , which we can in turn reinterpret as enumerative statements. Let us close this posts by giving an example of such phenomenon.

For a fixed integer , the set consists of functions $\latex f : I \longrightarrow [s]$ where each fibre is linearly ordered. Because we already computed that , we now compute that . Equating coefficients by means of the binomial series, we see there are such functions if .

To wrap things up, we have constructed ourselves a cocartesian symmetric monoidal category of (set valued) combinatorial species, and a cardinality functor from this category to the discrete category of powerseries that respects sums and products. In upcoming posts, we will shift our attention to module valued combinatorial species, where we can do some algebra.

*Add *(16/04*) *In [2] the reader can find a very nice example of counting with combinatorial species.