8.3 The Aldor Category of Combinatorial Species

  8.3.1 Structures and Isomorphismtypes

Before we come to concrete combinatorial species, we define which operations a species should export. Therefore, we start by defining a category. Clearly, for a combinatorial species F, we want to be able to construct for each set U the set F[U]. As explained above, we restrict the elements of U to belong to a type L. Looking at (2), we require an Aldor function structures (see below) that should be of type

Set L -> Set %

but our design uses

SetSpecies L -> Generator %

instead.

Note that CombinatorialSpecies and SetSpecies should be defined in the same file since they mutually depend on each other.

We have chosen Generator instead of the probably more natural Set as the result type, since, first, we expect that sets F[U] become so big that they might waste more computer memory than being interesting. And, second, we want to do ranking and unranking and thus must have a certain order on the generated elements so that they could be deterministically mapped to natural numbers.

As for the input, our first implementation really used Set, but in Set there is no order of elements and thus we cannot guarantee that the resulting generator generates structures always in the same order for identical input sets.

The problem with Set is that sets like {1,2} and {2,1} are mathematically identical and they are also considered equal as elements of Set, but not so in computer memory. Often sets are internally implemented as lists with the assertion that the elements are different. No order is assumed. And it cannot be assumed since the argument of the Set constructor is a type L that need not export an ordering function. So internally, the above sets are represented as the lists [1,2] and [2,1], respectively.

We would like the function structures return identical output for identical input. In other words, the resulting generator would have to generate the elements in the same order no matter whether it would be given the set {1,2} or the set {2,1} since

  1. they are identical as mathematical objects, and
  2. we would like to be able to speak about the n-th structure corresponding to a certain set of labels.

Placing the labels of the n-th structure differently, gives a different structure. However, without an ordering function we cannot bring the internal representation of {1,2} and {2,1} into a canonical form. That is the reason why we decided to introduce SetSpecies.

The domain SetSpecies is like Set, but with the additional assumption that for a list a of type List(L) with all distinct elements taken from L and with b defined by

b := (set(a) $ SetSpecies(L)) :: List(L)

the equality a = b of List holds.

In order to make the function structures deterministic, we say, if x and y of type SetSpecies(L) are two equal sets (equal in the sense of SetSpecies) and if furthermore

(x :: List L) = (y :: List L)

then structures(x) and structures(y) are generators that generate the same elements in the same order.

Since nothing is said about the (internal) order of elements in Set, we cannot use Set instead of SetSpecies.

If, for example,

x: SetSpecies Integer := set [1,2];
y: SetSpecies Integer := set [2,1];

then x = y and

(x :: List Integer) ~= (y :: List Integer)

and thus structures(x) and structures(y) are allowed to generate the corresponding combinatorial structures in a different order.

The function structures is the reason for putting the type L already in the category CombinatorialSpecies.

Type Constructor

CombinatorialSpecies

Usage

L == String;
Foo(L): CombinatorialSpecies(L) with {...} == add {...}

Parameters

L: LabelType

The type of objects that are used as labels.

Description

The category combinatorial species.

CombinatorialSpecies is the category of types that provide operations on combinatorial species.

An instance of a CombinatorialSpecies provides a way to generate and count labelled and unlabelled structures.

Remarks

ToDo 16 The unlabelled situation is not yet implemented.
71cat: CombinatorialSpecies 71  (55)
define CombinatorialSpecies(L: LabelType): Category == with {
        exports: CombinatorialSpecies 73
    default {
        defaults: CombinatorialSpecies 80
    }
}

Defines:
CombinatorialSpecies, used in chunks 55, 83–85, 90, 97, 107, 119, 127, 131a, 138, 147a, 166a, 175a, 182a, 191a, 194, 452, 455, 458b, 461, 626, 643–50, 652, 654, 655, 658, and 729.

Uses LabelType 62.

Exports of CombinatorialSpecies

generatingSeries: ExponentialGeneratingSeries Returns the exponential generating series of the species.

isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries Returns the type generating series.

cycleIndexSeries: CycleIndexSeries Returns the cycle index series.

structures: SetSpecies L -> Generator % Generates all structures for a given set of labels.

isomorphismTypes: SetSpecies L -> Generator % Generates all isomorphism types.

LabelType;

expression: SpeciesExpression Returns an expression for the species.

What do we want to express with that category? Of course, an Aldor category expresses the operations that are allowed for combinatorial species. Naturally, to each combinatorial species there are associated three series, namely

Export of CombinatorialSpecies

generatingSeries: ExponentialGeneratingSeries

Usage

L == Integer;
X == SingletonSpecies L;
gs: ExponentialGeneratingSeries := generatingSeries $ X;
import from Integer;
l: List Integer := [coefficient(gs, n) for n in 0..3];
e: List Integer := [0, 1, 0, 0];
assert(l = e);

Description

Returns the exponential generating series of the species.

73exports: CombinatorialSpecies 73  (71)  74
generatingSeries: ExponentialGeneratingSeries;

Uses ExponentialGeneratingSeries 316.

Export of CombinatorialSpecies

isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries

Usage

L == Integer;
X == EmptySetSpecies L;
gs: OrdinaryGeneratingSeries := generatingSeries $ X;
import from Integer;
l: List Integer := [coefficient(gs, n) for n in 0..3];
e: List Integer := [1, 0, 0, 0];
assert(l = e);

Description

Returns the type generating series.

74exports: CombinatorialSpecies 73+   (71)  73  75
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries;

Uses OrdinaryGeneratingSeries 311.

Export of CombinatorialSpecies

cycleIndexSeries: CycleIndexSeries

Description

Returns the cycle index series.

75exports: CombinatorialSpecies 73+   (71)  74  78
cycleIndexSeries: CycleIndexSeries;

Uses CycleIndexSeries 330.
8.3.1 Structures and Isomorphismtypes

Let us carry out an example that illustrates the notions of structures and isomorphismtypes. Consider the combinatorial species L of linear orders. I.e., given a set U of cardinality n, the species L produces all n! different linear orders of U. A bijection σ : U↦→V is simply a relabelling of a structure. For example, if we take U = {1,2,3}, L produces the structures L[{1,2,3}] = {123,132,213,231,312,321}.

The bijection σ = (

123
231
) maps the structure 132 to the structure 213, thus these two structures are isomorphic.

Now consider the species S of permutations. To make it more obvious that a species takes an arbitrary set, without inherent order, set U = {1,a,∗}. The structures produced by S when applied to this set are then

           { (1  a  ∗) (1  a  ∗) (1   a  ∗)
S[{1,a,∗}] =   1  a  ∗ , 1  ∗  a  , a  1  ∗ ,
             (       ) (       ) (        )}
              1  a  ∗ , 1  a  ∗  , 1  a  ∗   .
              a  ∗  1   ∗  1  a    ∗  a  1

The bijection σ = (

1a
a1
) maps the structure (
1a
1a
) to the structure (
a1
a1
) = (
1a
a1
), which are therefore isomorphic. On the other hand, the structure (
1a
1a
) is a fixed point of all bijections.

Export of CombinatorialSpecies

structures: SetSpecies L -> Generator %

Usage

s: List L := ...
for e in structures(s) repeat ...

Parameters

s: SetSpecies L

A set of labels.

Description

Generates all structures for a given set of labels.

In terms of [BLL98], this function generates the set F[U] for a species F and a finite set U. In the Aldor implementation we have the restriction that the elements of U must be of the same type L.

Instead of returning a Set structure, we just require being able to generate the structures. Using Generator, we do not need to store a huge amount of data in memory.

78exports: CombinatorialSpecies 73+   (71)  75  79a
structures: SetSpecies L -> Generator %;

Uses Generator 617 and SetSpecies 117.

Export of CombinatorialSpecies

isomorphismTypes: SetSpecies L -> Generator %

Description

Generates all isomorphism types.

ToDo 17
rhx 11 14-Aug-2006: It is not yet clear what the type of this function/constant should be. In general, isomorphism types are equivalence classes of structures. It could be reasonable to say that isomorphismTypes returns (unique) representatives of these classes. (The unique is probably a tough thing, since we might have no order on the input set or on L in general.
79aexports: CombinatorialSpecies 73+   (71)  78  79b
isomorphismTypes: SetSpecies L -> Generator %;

Uses Generator 617 and SetSpecies 117.

We want to be able to use combinatorial species as labels.

79bexports: CombinatorialSpecies 73+   (71)  79a  81
LabelType;

Uses LabelType 62.
80defaults: CombinatorialSpecies 80  (71)
elements(): Generator % == generate {
        l: List L := empty;
        for label: L in elements()$L repeat {
                l := cons(label, l);
                s: SetSpecies L := set reverse l;
                for e: % in structures s repeat yield e;
        }
}

Uses Generator 617 and SetSpecies 117.

Export of CombinatorialSpecies

expression: SpeciesExpression

Description

Returns an expression for the species.

expression returns an expression for the species, where the species itself is denoted with the string ”Self”.

81exports: CombinatorialSpecies 73+   (71)  79b
expression: SpeciesExpression;

Uses SpeciesExpression 430.