Species

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 M,   A(f) is called the transport of A-structures along f. The elements of M are called points, and the elements aÎA(M) are called elements of A, which is abbreviated by aÎA. Let us consider a bunch of examples before we go into details.

Examples:  

• The species labelled graphs G is defined by

  G(M):={g | g labelled graph with vertex set M},

  and G(f) maps gÎG(M) onto

  g':=G(f)(g),

  where g' arises from g by simply replacing the label mÎM by the label f(m)ÎN, for each bijection f between M and N.
• The species permutations S is defined by mapping M onto the symmetric group S_M on M:

  S(M):=S_M={p:M -> M | p is bijective},

  and S(f) is defined to be renumbering according to f, which means that, for each pÎS_M, we have

  S(f)(p):=f o p o f^-1ÎS_N, for fÎMor(M,N).

• The species linear orders L maps M onto the set of all the | M | ! linear orders on M:

  L(M):={(m_i1<...<m_{i | M |} ) | m_in ÎM, m_in not = m_im,n not =m}.

  The morphism L(f) means simply replacing m by f(m):

  L(f)(m_i1<...<m_{i | M |} ):=(f(m_i1)<...<f(m_{i | M |} )).

• The species set E is defined by

  E(M):={M}, E(f)(M):=f(M).

• The empty species Æ maps each M onto the empty set and therefore Æ(f) must always be the empty mapping.
• The species empty set 1 maps the set Æ onto {Æ}, and all the other M onto Æ, so that each morphism f not =Æ is mapped onto the empty mapping Æ, while the empty mapping, being an element of Mor(Æ,Æ), is mapped onto the identity mapping on {Æ}.
• The species singleton X is defined by

  X(M):={m} if M={m}

  X(M):=Æ otherwise

  and

  X(f):=1_M if M={m}

  X(f):=Æ otherwise

• The species endofunctions F maps M onto M^M, while, for each f in Mor(M,N) we put

  F(f)(j):=f o j o f^-1ÎN^N, for each jÎM^M.

• The species F₀, the endofunctions with fixed point, maps M onto

  F₀(M):={jÎM^M | $mÎM:j(m)=m},

  while F₀(f)(j)=f o j o f^-1, as before.
• The species idempotent endofunctions K maps M onto the following subset of F(M):

  K(M):={jÎM^M | j²=j},

  and again it has 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 species labelled trees T maps n onto the set

T(n):={g | g tree with vertex set n},

and g'=T(f)(g) is the tree obtained from g by replacing the label iÎn by f(i)ÎN, if fÎMor(n,N). Correspondingly the species labelled rooted trees T₀ is defined by

T₀(n):={t:=(g,i) | gÎT(n),iÎn},

the element i of (g,i) is called the root of t.

Using this fact that it suffices, up to relabeling, to describe A(n), we introduce, for each species A, the corresponding generating function called the cardinality of A:

A(x):=å_nÎN | A(n) | (xⁿ)/(n!).

Examples: For the cardinalities of the preceding examples we have:

G(x)=å_n2^{[n choose 2]}(xⁿ)/(n!), S(x)=L(x)=(1)/(1-x), E(x)=e^x,

Æ(x)=0, 1(x)=1, X(x)=x, F(x)=å_nnⁿ(xⁿ)/(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 species S of permutations and the species L of linear orders are equipotent. Let us assume that there exist bijections Q_n:S(n) -> L(n), which satisfy

L(f) o Q_n=Q_n o S(f),

for each bijection f:n -> n. Consider an n>1, a bijection f which is not the identity mapping, and apply both sides of the identity to p:=1ÎS_n =S(n). The left hand side yields, if

Q_n(p)=:(i₁<...<i_n)ÎL(n),

that

(L(f) o Q_n)(p)=L(f)(i₁<...<i_n)=(f(i₁)<...<f(i_n)),

while an application of the right hand side gives

(Q_n o S(f))(p)=Q_n(f o p o f^-1)=Q_n (1)

=(i₁<...<i_n) not =(f(i₁)<...<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(f) and B(f), where f in both cases runs through the bijective f:n -> n. The multiplication uses the cartesian product:

(A·B)(n):=È_{M DOTCUP N=n}A(M)´B(N)=È_MÍnA(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 (pg), where p is a permutation, say (135)ÎS_M, M:={1,3,5}, and g is a labelled graph on N={2,4,6,7}, with edge set {{2,3},{3,5}}. We use this notation also in order to illustrate the plethysm B A, defined as follows:

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

where the disjoint union is taken over all the set partitions p of n. For example, an element of B A(6), arising from the partition p:={{1,4,5},{2,6},{3}} looks as follows:

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^mX(p_i)´A(m),

but X(p_i) is empty except when | p_i | =1, so that this union is in fact taken over the single partition p={{1},..., {n}} of n, and therefore

(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^j1 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 *, and then applying A:

A'(n):=A(n⁺), where n⁺:=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 S_n \\A(n), so that we obtain a transversal

T(A):=È_nÎNT_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ⁿ.

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₁,x₂,...):=å_aÎT(A)C((S_n )_a,n; x₁,x₂,...),

where (S_n )_a denotes the stabilizer of aÎA(n) in S_n . Hence, for example (exercise):

  Z_X=x₁, Z_E=exp(å_i(x_i)/(i)), Z_L=(1)/(1-x₁), Z_S= Õ_i(1)/(1-x_i) .

Since

C((S_n )_a,n;x₁,0,...)=(1)/( | (S_n )_a | )x₁ⁿ,

and

C((S_n )_a,n;x,x²,x³,...)=xⁿ,

we obtain

  Z_A(x,0,...)=A(x), and Z_A(x,x²,x³,...)=[~A] (x).

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

Species