Species |

Consider the category *F* of *finite sets with bijections*. It
consists of the two classes *Obj(F)* of *objects* *M,N,...*, the
finite sets, and the class *Mor(F)* of *morphisms* *f,g,...*,
which are the bijections between finite sets. *Mor(M,N)* denotes the set of
morphisms between the sets *M* and *N*:

(Note that the categorical definition of mappings identifiesMor(M,N):={f:M -> N | f is a bijection}.

which is associative. In our case this is of course the usual composition of mappings. Furthermore the definition of category requires a neutral elemento :Mor(L,M)´Mor(M,N) -> Mor(L,N):(f,g) -> g o f,

A *species* *A* is a (covariant) functor on *F*. This
means the following: *A* consists of a mapping from *Obj(F)* to *Obj(F)*, which we also denote by *A*, for sake of simplicity of notation, together
with a mapping from *Mor(F)* to *Mor(F)* which will be denoted by
*A*, too:

andA:Obj(F) -> Obj(F):M -> A(M),

whereA:Mor(F) -> Mor(F):f -> A(f),

The setA(g o f)=A(g) o A(f), and A(1_{M})=1_{A(M)}.

Examples:

- The species
labelled graphsGis defined byandG(M):={g | g labelled graph with vertex setM},G(f)mapsgÎG(M)ontowhereg':=G(f)(g),g'arises fromgby simply replacing the labelmÎMby the labelf(m)ÎN, for each bijectionfbetweenMandN.- The species
permutationsSis defined by mappingMonto the symmetric groupSon_{M}M:andS(M):=S_{M}={p:M -> M | p is bijective},S(f)is defined to berenumbering according to, which means that, for eachfpÎS, we have_{M}S(f)(p):=f o p o f^{-1}ÎS_{N}, for fÎMor(M,N).- The species
linear ordersLmapsMonto the set of all the| M | !linear orders onM:The morphismL(M):={(m_{i1}<...<m_{i | M | }) | m_{in}ÎM, m_{in}not = m_{im},n not =m}.L(f)means simply replacingmbyf(m):L(f)(m_{i1}<...<m_{i | M | }):=(f(m_{i1})<...<f(m_{i | M | })).- The species
setEis defined byE(M):={M}, E(f)(M):=f(M).- The
empty speciesÆmaps eachMonto the empty set and thereforeÆ(f)must always be the empty mapping.- The species
empty set1 maps the setÆonto{Æ}, and all the otherMontoÆ, so that each morphismf not =Æis mapped onto the empty mappingÆ, while the empty mapping, being an element ofMor(Æ,Æ), is mapped onto the identity mapping on{Æ}.- The species
singletonXis defined byX(M):={m} if M={m}andX(M):=Æ otherwiseX(f):=1_{M}if M={m}X(f):=Æ otherwise- The species
endofunctionsFmapsMontoM, while, for each^{M}finMor(M,N)we putF(f)(j):=f o j o f^{-1}ÎN^{N}, for each jÎM^{M}.- The species
F, the_{0}endofunctions with fixed point, mapsMontowhileF_{0}(M):={jÎM^{M}| $mÎM:j(m)=m},F, as before._{0}(f)(j)=f o j o f^{-1}- The species
idempotent endofunctionsKmapsMonto the following subset ofF(M):and again it hasK(M):={jÎM^{M}| j^{2}=j},K(f):=f o j o f.^{-1}

Let us return to the consideration of a general species *A* again. We recall
that it maps a morphism *f:M -> N* onto *A(f)*, which is a bijection
from *A(M)* onto *A(N)*. We may therefore call *A(f)* a *relabeling* of the *a* in *A(M)*, so that the *A*-structures on
*N* arise
from the *A*-structures on *M* by relabeling. *Thus it suffices (up to
relabeling) to define A on each of the sets n, where nÎN.*

Using this fact that it suffices, up to relabeling, to describeExamples:The specieslabelled treesTmapsonto the setnandT(n):={g | g tree with vertex setn},g'=T(f)(g)is the tree obtained fromgby replacing the labeliÎbynf(i)ÎN, iffÎMor(. Correspondingly the speciesn,N)labelled rooted treesTis defined by_{0}the elementT_{0}(n):={t:=(g,i) | gÎT(n),iÎn},iof(g,i)is called therootoft.

A(x):=å_{nÎN}| A(n) |(x^{n})/(n!).

Correspondingly two speciesExamples:For the cardinalities of the preceding examples we have:G(x)=å_{n}2^{[n choose 2]}(x^{n})/(n!), S(x)=L(x)=(1)/(1-x), E(x)=e^{x},Æ(x)=0, 1(x)=1, X(x)=x, F(x)=å_{n}n^{n}(x^{n})/(n!).

A stronger condition isA~B.

in which we require canonic bijectionsA simeq B,

It is clear that the following holds:B(f) o Q_{M}=Q_{N}o A(f), for each fÎMor(M,N).

The converse is not true, as it is shown byA simeq BÞA~B.

We shall now use set theoretic operations in order to introduce on the isomorphism classes of species a semiring structure. The operation ofExample:Clearly the speciesSof permutations and the speciesLof linear orders are equipotent. Let us assume that there exist bijectionsQ, which satisfy_{n}:S(n) -> L(n)for each bijectionL(f) o Q_{n}=Q_{n}o S(f),f:. Consider ann->nn>1, a bijectionfwhich is not the identity mapping, and apply both sides of the identity top:=1ÎS. The left hand side yields, if_{n}=S(n)thatQ_{n}(p)=:(i_{1}<...<i_{n})ÎL(n),while an application of the right hand side gives(L(f) o Q_{n})(p)=L(f)(i_{1}<...<i_{n})=(f(i_{1})<...<f(i_{n})),(Q_{n}o S(f))(p)=Q_{n}(f o p o f^{-1})=Q_{n}(1)=(i_{1}<...<i_{n}) not =(f(i_{1})<...<f(i_{n})).

The species(A+B)(n):=A(n) DOTCUP B(n).

Since a set(A·B)(n):=È_{M DOTCUP N=n}A(M)´B(N)=È_{MÍn}A(M)´B(n\M).

The necessary checks are straightforward. But there are several other important operations on species. Before we start defining these let us introduce a helpful notation which allows us to illustrate the various situations. In order to sketch anLemma:The isomorphism classes of species form a semiring with respect to addition and multiplication. The neutral element with respect to addition is the empty speciesÆwhile the neutral element with respect to multiplication is the species empty set 1.

the *a* and the box maybe left out, so that an element of
*(A+B)( 4)* is of the following form:

while an element of *(A·B)( 5)* looks as follows:

for example, an element of

where the disjoint union is taken over all the set partitions(B A)(n):=È_{p={p1,...,pm}}Õ_{i=1}^{m}B(p)´A(_{i}m),

The plethysm of structures has many interesting properties, for example the singleton

Proof: We obtain from the definition of plethysm thatA simeq X A simeq A X.

but(X A)(n)=È_{p}Õ_{i=1}^{m}X(p)´A(_{i}m),

It is quite often helpful to recognize species as plethysms of species. For example, if(X A)(n)=A(n).

then obviouslyC(n):={sÎS(n) | " 0<j<n:s^{j}1 not =1},

since each permutation is a union of its disjoint cyclic factors. This motivates us to say that, in caseS simeq C E,

whereG simeq Z E,

Another interesting notion is that of the *derivative*. It associates with *A* the
species *A'*, which is obtained by adding to the set * n* a further and
anonymous element, we indicate it by

A further helpful concept is that ofA'(n):=A(n^{+}), wheren^{+}:=nÈ{*}.

The corresponding generating functions clearly satisfyA_{·}(n):=A(n)´n.

So far each elementA'(x)=(d)/(dx)A(x), A_{·}(x)=x·(d)/(dx)A(x).

An orbit is called aS_{n}´A(n) -> A(n):(s,a) -> A(s)a.

of all the types ofT(A):=È_{nÎN}T_{n}(A)

is called the species[~A] (n):={(s,a) | aÎA(n),sÎS_{n}:A(s)a=a}

And hence the ordinary generating function for the[~A] (x):=å_{nÎN}| T_{n}(A) | x^{n}.

Now we would like to apply to species what we know about cycle indicator polynomials. For this purpose we introduce the following formal power series:

whereZ_{A}:=Z_{A}(x_{1},x_{2},...):=å_{aÎT(A)}C((S_{n})_{a},n; x_{1},x_{2},...),

SinceZ_{X}=x_{1}, Z_{E}=exp(å_{i}(x_{i})/(i)), Z_{L}=(1)/(1-x_{1}), Z_{S}= Õ_{i}(1)/(1-x_{i}).

andC((S_{n})_{a},n;x_{1},0,...)=(1)/(| (S_{n})_{a}|)x_{1}^{n},

we obtainC((S_{n})_{a},n;x,x^{2},x^{3},...)=x^{n},

Z_{A}(x,0,...)=A(x), and Z_{A}(x,x^{2},x^{3},...)=[~A] (x).

E:Provethe correctness of the cycle index series above..

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

Species |