Species |

There are many ways to formalize the evaluation of generating functions and canonic constructions using recursion, disjoint union, cartesian product formation and other set theoretic procedures. A good survey over many of these methods gives the book by Goulden and Jackson. Another method makes use of the notion of species, it will be described next.

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*:

Mor(M,N):={f:M -> N | f is a bijection}.

(Note that the categorical definition of mappings identifies *f:M -> N*
with the *triple* *(M,{(m,f(m)) | mÎM},N)*, and hence, if *(M,N) not =
(M',N')*, then *Mor(M,N)ÇMor(M',N')=Æ*.) Moreover the
definition of category assumes a multiplication

o :Mor(L,M)´Mor(M,N) -> Mor(L,N):(f,g) -> g o f,

which is associative. In our case this is of course the usual composition of
mappings. Furthermore the definition of category requires a neutral element
*1 _{M}ÎMor(M,M)* (neutral with respect to the multiplication mentioned above),
it is the identity mapping here.

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:

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

and

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

where *A(f)ÎMor(A(M),A(N))*, and such that

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

The set *A(M)* is called the set of *labelled A-structures* on

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

Examples: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.

Using this fact that it suffices, up to relabeling, to describe *A( n)*, we
introduce, for each species

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

Examples: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!).

Correspondingly two species *A* and *B* are called *equipotent*, if and
only if *A(x)=B(x)*. We abbreviate this by writing

A~B.

A stronger condition is *isomorphy*, for short:

A simeq B,

in which we require canonic bijections *Q _{M}:A(M) -> B(M)* which
satisfy

B(f) o Q_{M}=Q_{N}o A(f), for each fÎMor(M,N).

It is clear that the following holds:

A simeq BÞA~B.

The converse is not true, as it is shown by

Example: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})).

We shall now use set theoretic operations in order to introduce on the
isomorphism classes of species a semiring structure. The operation of *addition* is defined by disjoint union as follows:

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

The species *A+B*, called the *species sum* of *A* and *B*, or simply the
*sum* of *A* and *B*, has as its set of transport on * n* the disjoint
union of the set of mappings

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

Since a set *R* together with operations *+* and *·* is called a
*semiring* if and only if both *(R,+)* and *(R,·)* are commutative
semigroups, 0 is neutral with respect to *+*, 1 is neutral with respect to
*·*, *0r=0*, for each *rÎR*, and the distributivity law *(r+s)t=rt+rs*
holds, we obtain

Lemma: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 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 an *A*-structure *aÎA( 4)*, say, we write

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 *(S·G)( 7)* is such
a pair

(B A)(n):=È_{p={p1,...,pm}}Õ_{i=1}^{m}B(p)´A(_{i}m),

where the disjoint union is taken over all the set partitions *p* of
* n*. For example, an element of

The plethysm of structures has many interesting properties, for example
the singleton *X* is neutral with respect to plethysm:

A simeq X A simeq A X.

Proof: We obtain from the definition of plethysm that

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

but *X(p _{i})* is empty except when

(X A)(n)=A(n).

It is quite often helpful to recognize species as plethysms of species. For
example, if *C* denotes the species of cyclic permutations, i.e.

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

then obviously

S simeq C E,

since each permutation is a union of its disjoint cyclic factors. This
motivates us to say that, in case *A simeq B E*, *B* is the species
of *connected*
*A*-structures.
An example is the decomposition of labelled graphs into their
connected components:

G simeq Z E,

where *Z* denotes the species *connected graphs*
.

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'(n):=A(n^{+}), wheren^{+}:=nÈ{*}.

A further helpful concept is that of *punctuation*, where *A* is mapped onto

A_{·}(n):=A(n)´n.

The corresponding generating functions clearly satisfy

A'(x)=(d)/(dx)A(x), A_{·}(x)=x·(d)/(dx)A(x).

So far each element *aÎA* is a *labelled* structure, for example
a labelled graph. In order to get rid of the labeling we have of course to
introduce the canonical action

S_{n}´A(n) -> A(n):(s,a) -> A(s)a.

An orbit is called a
*type*
of *A*-structure. Furthermore we denote by
*T _{n}(A)*
a transversal of

T(A):=È_{nÎN}T_{n}(A)

of all the types of *A*-structures.
The set

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

is called the species *associated*
with *A*.
Its generating function *[~A] * is

[~A] (x):=å_{nÎN}| T_{n}(A) | x^{n}.

And hence the ordinary generating function
for the *A*-types is the exponential
generating function for the species *[~A] *.

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:

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

where *(S _{n} )_{a}* denotes the stabilizer of

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

Since

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

and

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

we obtain

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 "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

Species |