Species

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:

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

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

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

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

A(g o f)=A(g) o A(f), and A(1_M)=1_A(M).

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.

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

A~B.

A simeq B,

B(f) o Q_M=Q_N o A(f), for each fÎMor(M,N).

  A simeq BÞA~B.

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

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

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

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

B A

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

B A(6)

  A simeq X A simeq A X.

(X A)(n)=È_pÕ_i=1^mX(p_i)´A(m),

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

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

S simeq C E,

A simeq B E

G 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 *, and then applying A:

A'(n):=A(n⁺), where n⁺:=nÈ{*}.

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

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

S_n ´A(n) -> A(n):(s,a) -> A(s)a.

T(A):=È_nÎNT_n(A)

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

[~A] (x):=å_nÎN | T_n(A) | xⁿ.

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₂,...),

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

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

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

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

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

Species