#### 8.4 Basic Species

##### 8.4.1 The Empty Set Species

The species 1 (cf. [BLL98, p. 8]), characteristic of the empty set is defined by

 (3)

Type Constructor

ToDo 18 Add proper usage code.

Usage

import from EmptySetSpecies(L);

Description

The species that represents the characteristic of the empty set.

83dom: EmptySetSpecies 83  (55)
EmptySetSpecies(L: LabelType): CombinatorialSpecies L == {
import from String;
expression: SpeciesExpression == leaf "EmptySetSpecies";
}
}

Defines:
EmptySetSpecies, used in chunks 194, 455, 458b, 629, 641–43, 645, and 647.

Uses CharacteristicSpecies 85, CombinatorialSpecies 71, Integer 66, LabelType 62, SpeciesExpression 430, and String 65.
##### 8.4.2 The Singleton Species

The species X (cf. [BLL98, p. 8]), characteristic of singletons is defined by

 (4)

Type Constructor

ToDo 19 Add proper usage code.

Usage

import from SingletonSpecies(L);

Description

The species that represents the characteristic of singletons.

84dom: SingletonSpecies 84  (55)
SingletonSpecies(L: LabelType): CombinatorialSpecies L == {
import from String;
expression: SpeciesExpression == leaf "SingletonSpecies";
}
}

Defines:
SingletonSpecies, used in chunks 88, 194, 455, 641–48, 650, 652, 658, 731, and 732.

Uses CharacteristicSpecies 85, CombinatorialSpecies 71, Integer 66, LabelType 62, SpeciesExpression 430, and String 65.
##### 8.4.3 The Characteristic Species

Type Constructor

Usage

import from Integer;
EmptySetSpecies(L: LabelType): CombinatorialSpecies L == {
}
SingletonSpecies(L: LabelType): CombinatorialSpecies L == {
}

Description

The species that represents cardinality characteristics of sets.

According to [BLL98, p. 30], each species F gives rise canonically to an enumerable family (Fn)n0 of species defined by setting for each n ,

 (5)
The species Fn is said to be the species F restricted to n.

If we denote by E the species of (finite) sets (given by the constructor SetSpecies) then CharacteristicSpecies represents En. In other words, the domain CharacteristicSpecies(L, n) can be thought of as the species SetSpecies(L) restricted to n.

85dom: CharacteristicSpecies 85  (55)
CharacteristicSpecies(n:Integer)(L:LabelType): CombinatorialSpecies L == add {
Rep == SetSpecies L;
import from Rep;
nn: I == machine n;
implementation: CharacteristicSpecies 86a
}

Defines:
CharacteristicSpecies, used in chunks 83, 84, 455, 630, and 631.

Uses CombinatorialSpecies 71, I 47, Integer 66, LabelType 62, and SetSpecies 117.
86aimplementation: CharacteristicSpecies 86a  (85)  86b
structures(s: SetSpecies L): Generator % == {
import from I;
generate if #s = nn then yield per s;
}

Uses Generator 617, I 47, and SetSpecies 117.
86bimplementation: CharacteristicSpecies 86a+   (85)  86a  86c
generatingSeries: ExponentialGeneratingSeries == {
import from Q, DataStream Z;
term(inv factorialStream(nn), nn);
}

Uses DataStream 386, ExponentialGeneratingSeries 316, Q 47, and Z 47.
86cimplementation: CharacteristicSpecies 86a+   (85)  86b  87a
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == term(1, nn);

Uses OrdinaryGeneratingSeries 311.
87aimplementation: CharacteristicSpecies 86a+   (85)  86c  87b
cycleIndexSeries: CycleIndexSeries == {
term(coefficient(cycleIndexSeries\$SetSpecies(L), nn), nn);
}

Uses CycleIndexSeries 330 and SetSpecies 117.
87bimplementation: CharacteristicSpecies 86a+   (85)  87a  87c
isomorphismTypes: SetSpecies L -> Generator % == structures;

Uses Generator 617 and SetSpecies 117.
87cimplementation: CharacteristicSpecies 86a+   (85)  87b  87d
(x: %) = (y: %): Boolean == rep x = rep y;
87dimplementation: CharacteristicSpecies 86a+   (85)  87c  88
(tw: TextWriter) << (x: %): TextWriter == {
import from L, String;
empty? rep x => tw << "nil";
empty? rest rep x => tw << first rep x;
tw << rep x;
}

Uses String 65.
88implementation: CharacteristicSpecies 86a+   (85)  87d
import from String;
expression: SpeciesExpression == leaf "SingletonSpecies" ^ leaf n;

Uses SingletonSpecies 84, SpeciesExpression 430, and String 65.
##### 8.4.4 The Species of Linear Orders

Definition 8.2. [BLL98, Chp. 1.1] The species L which fulfils the equation L = 1 + X L is called the species of linear orders. For any bijection σ : U V , with U = the bijection L[σ] : L[U] L[V ] is given by L[σ]([u1,,ln]) = [σ(u1),(un)].

The species of linear order is also knows as the species of lists or the species of sequences.

Type Constructor

Usage

macro Z == Integer;
s: SetSpecies Z := [2, 3, 5];
for x in structures(s)\$LinearOrder(Z) repeat {
stdout << x << newline;
}

Description

89dom: LinearOrder 89  (55)
LinearOrder(L: LabelType): with {
exports: LinearOrder 90
} == List L add {
Rep == List L;
import from Rep;
implementation: LinearOrder 91b
}

Defines:
LinearOrder, used in chunks 94, 100a, and 635.

Uses LabelType 62.

Exports of LinearOrder

coerce: % -> List L Coerces to a List.

90exports: LinearOrder 90  (89)  91a
CombinatorialSpecies L;

Uses CombinatorialSpecies 71.

Export of LinearOrder

coerce: % -> List L

Description

Coerces to a List.

91aexports: LinearOrder 90+   (89)  90
coerce: % -> List L;
91bimplementation: LinearOrder 91b  (89)  91c
coerce(x: %): List L == rep x;
91cimplementation: LinearOrder 91b+   (89)  91b  92b
generation of lists 92a
structures(s: SetSpecies L): Generator % == generate {
for l in lists(s :: List L) repeat yield per l;
}

Uses Generator 617 and SetSpecies 117.

We generate all lists in a recursive fashion. We walk through the given list l and then do the following for each element c of the list.

1. Take out one element c from l.
2. Generate all lists that do not contain c.
3. For each of these generated lists, c is prepended as the first element and the resulting list is yielded.
4. Put c back to l in the same position as it was before.
92ageneration of lists 92a  (91c)
local lists(l: List L): Generator List L == generate {
empty? l => yield l;
current := l;
c := first current;
for u in lists(rest l) repeat yield cons(c, u);
assert(not empty? current);
while not empty?(tmp := rest current) repeat {
c := first current;
setRest!(current, rest tmp); -- remove c from l
for u in lists l repeat yield cons(c, u);
setRest!(current, tmp); -- put c back into l
current := tmp;
}
}

Uses Generator 617.
92bimplementation: LinearOrder 91b+   (89)  91c  93a
isomorphismTypes(s: SetSpecies L): Generator % == generate {
yield per(s :: List(L));
}

Uses Generator 617 and SetSpecies 117.

The generating series is L(x) = = 1 + x + x2 + .

93aimplementation: LinearOrder 91b+   (89)  92b  93b
generatingSeries: ExponentialGeneratingSeries == {
(stream(1\$Q)\$DataStream(Q)) :: ExponentialGeneratingSeries;
}

Uses DataStream 386, ExponentialGeneratingSeries 316, and Q 47.

The isomorphism type generating series is also given by (x) = .

93bimplementation: LinearOrder 91b+   (89)  93a  93c
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == {
(stream(1\$Z)\$DataStream(Z)) :: OrdinaryGeneratingSeries;
}

Uses DataStream 386, OrdinaryGeneratingSeries 311, and Z 47.

The cycle index series ZL of the species L of linear orders is given by

 (6)
93cimplementation: LinearOrder 91b+   (89)  93b  94
local cisGenerator: Generator P == generate {
import from I, T, P;
x1: V := 1::V;
for n: I in 0.. repeat yield power(x1, n) :: P;
}
cycleIndexSeries: CycleIndexSeries == cisGenerator :: CycleIndexSeries;

Uses CycleIndexSeries 330, Generator 617, and I 47.
94implementation: LinearOrder 91b+   (89)  93c
import from String;
expression: SpeciesExpression == leaf("LinearOrder");

Uses LinearOrder 89, SpeciesExpression 430, and String 65.
##### 8.4.5 The Species of Cyclic Permutations

Let S[U] = be the set of bijections on U.

Definition 8.3. [BLL98, Chp. 1.1] The species C of cyclic permutations or oriented cycles is defined by

 (7)
for any finite set U with card(U) = n. In particular, C[] = . For any bijection σ : U V , C[σ] is given by C[σ](ϕ) = σ ϕ σ1.

The species of cyclic permutations is closely related to the species of linear orders as can be seen by the generation of structures below.

ToDo 20
rhx 12 24-Mar-2007: Whenever the derivative of species is implemented then we should put here the relation
 (8)
where L is the species of linear orders, see Example 1.4.7 in [BLL98].

Type Constructor

Usage

macro Z == Integer;
s: SetSpecies Z := [2, 3, 5];
for x in structures(s)\$Cycle(Z) repeat stdout << x << newline;

Description

96dom: Cycle 96  (55)
Cycle(L: LabelType): with {
exports: Cycle 97
} == List L add {
Rep == List L;
import from I, Rep;
implementation: Cycle: auxiliary functions 103a
implementation: Cycle 98b
}

Defines:
Cycle, used in chunks 104b, 109, 110b, 637, and 649.

Uses I 47 and LabelType 62.

Exports of Cycle

coerce: % -> List L Coerce an oriented cycle to a list structure.

cycle: List L -> % Coerce a list structure into an oriented cycle.

97exports: Cycle 97  (96)  98a
CombinatorialSpecies L;

Uses CombinatorialSpecies 71.

Export of Cycle

coerce: % -> List L

Description

Coerce an oriented cycle to a list structure.

98aexports: Cycle 97+   (96)  97  99a
coerce: % -> List L;
98bimplementation: Cycle 98b  (96)  99b
coerce(x: %): List L == rep x;

Export of Cycle

cycle: List L -> %

Description

Coerce a list structure into an oriented cycle.

ToDo 21
rhx 13 23-Mar-2007: Maybe this is a dangerous function and should be avoided. The question is, how canonical the representation is and how complex this function should be. It currently is O(1), but I am not sure that it is usually doable in that time. This function is similar to set. And we deliberately do not call it coerce.
99aexports: Cycle 97+   (96)  98a
cycle: List L -> %;
99bimplementation: Cycle 98b+   (96)  98b  100a
cycle(l: List L): % == per l;

We can generate all cycles by taking away from s one element u, generate all possible lists of the remaining elements and putting u as the first element of all these generated lists.

100aimplementation: Cycle 98b+   (96)  99b  100b
structures(s: SetSpecies L): Generator % == generate {
import from LinearOrder L;
if not empty? s then {
l: List L := s :: List L;
u := first l;
for t in structures(set rest l)\$LinearOrder(L) repeat {
yield per cons(u, t :: List L);
}
}
}

Uses Generator 617, LinearOrder 89, and SetSpecies 117.

The isomorphism types of cyclic permutations are like those of LinearOrder or SetSpecies, except that there is no structure on the empty set.

100bimplementation: Cycle 98b+   (96)  100a  101a
isomorphismTypes(s: SetSpecies L): Generator % == generate {
if not empty? s then yield per(s :: List L);
}

Uses Generator 617 and SetSpecies 117.

The generating series is

 (9)
We know that the order of the series is 1 and therefore use the function new to create the series and tell about the order.
101aimplementation: Cycle 98b+   (96)  100b  101b
local cycleOrder(): SeriesOrder == 1 :: SeriesOrder;
egsCycle(ao: I): Generator Q == generate {
import from Z, Q;
yield 0;
for n:I in 1.. repeat yield inv(n :: Z);
}
generatingSeries: ExponentialGeneratingSeries == new(egsCycle, cycleOrder);

Uses ExponentialGeneratingSeries 316, Generator 617, I 47, Q 47, SeriesOrder 289, and Z 47.

The isomorphism type generating series is given by (x) = .

101bimplementation: Cycle 98b+   (96)  101a  102
ogsCycle(ao: I): Generator Z == generate {yield 0\$Z; yield 1\$Z};
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == {
new(ogsCycle, cycleOrder);
}

Uses Generator 617, I 47, OrdinaryGeneratingSeries 311, and Z 47.

The cycle index series ZC of the species C of permutations is given by

 (10)
Since log(1 x) = m=1 we can easily derive
 ZC(x1,x2,…) = ∑ k=1∞∑ m=1∞ = ∑ n=1∞∑ = ∑ n=1∞∑ k|nϕ(k)xkn∕k.
We implement the last form of the sum, but we rather sum over all m = n∕k, because in that way addition to p always adds bigger terms (in the term order on T) later.
102implementation: Cycle 98b+   (96)  101b  104b
cycleIndexSeries: CycleIndexSeries == new(cisCycle, cycleOrder);

Uses CycleIndexSeries 330.

The following function generates all coefficients of the series. It starts with index 0.

103aimplementation: Cycle: auxiliary functions 103a  (96)
local cisCycle(ao: I): Generator P == generate {
macro PrimePowerProduct == SparseIndexedPowerProduct(I, I);
implementation: Cycle: cisCoefficient 103b
yield 0\$P;
for n:I in 1.. repeat yield cisCoefficient(n);
}

Uses Generator 617, I 47, PrimePowerProduct 307, and SparseIndexedPowerProduct 506.

Let us start with an auxiliary function for cisCoefficient which is the inverse of factor, i. e., multiply converts a prime power product into the corresponding integer.

103bimplementation: Cycle: cisCoefficient 103b  (103a)  104a
local multiply(k: PrimePowerProduct): I == {
r: I := 1;
for ep in k repeat {(e, p) := ep; r := r * p^e}
r;
}

Uses I 47 and PrimePowerProduct 307.

For the workaround see ToDo 10.

104aimplementation: Cycle: cisCoefficient 103b+   (103a)  103b
local cisCoefficient(n: I): P == BugWorkaround(
PrimePowerProduct has with {
divisors: % -> Generator %;
/: (%, %) -> %;
}
){
import from Z, V, SmallIntegerTools;
nn: PrimePowerProduct := factor n;
p: P := 0;
for m in divisors nn repeat {
k: PrimePowerProduct := nn/m;
q: Q := (eulerPhi(k) :: Z) / (n :: Z);
xk: V := multiply(k) :: V;
t: T := power(xk, multiply m);
p := [q, t]\$P + p;
}
p;
}

Uses BugWorkaround 48, Generator 617, I 47, PrimePowerProduct 307, Q 47, SmallIntegerTools 555, and Z 47.
104bimplementation: Cycle 98b+   (96)  102
import from String;
expression: SpeciesExpression == leaf("Cycle");

Uses Cycle 96, SpeciesExpression 430, and String 65.
##### 8.4.6 The Species of Permutations

Definition 8.4. [BLL98, Chp. 1.1] The species S of permutations (bijective endofunctions) is defined by S[U] = for any finite set U. For any bijection σ : U V , S[σ] is given by S[σ](ϕ) = σ ϕ σ1.

The species of permutations is closely related to the species of linear orders. However, their isomorphism types are different and, therefore, we cannot use List as the representation but rather have to use the following in accordance with the representation of Partition. For the generation of isomorphism types we can easily borrow from the code for Partition. In fact, each list in the array presents a cycle in the cycle decomposition of a given permutation.

105representation: Permutation 105  (106)
Rep == Array List L;

Uses Array 599.

Type Constructor

Usage

macro Z == Integer;
s: SetSpecies Z := [2, 3, 5];
for x in structures(s)\$Permutation(Z) repeat {
stdout << x << newline;
}

Description

106dom: Permutation 106  (55)
Permutation(L: LabelType): with {
exports: Permutation 107
representation: Permutation 105
import from Rep;
implementation: Permutation: auxiliary functions 110b
implementation: Permutation 108b
}

Defines:
Permutation, used in chunks 54, 114, 639, and 649.

Uses LabelType 62.

Exports of Permutation

coerce: % -> Array List L Coerces internal representation to an array of lists.

coerce: % -> SetSpecies Cycle L Coerces internal representation to a set of cycles.

107exports: Permutation 107  (106)  108a
CombinatorialSpecies L;

Uses CombinatorialSpecies 71.

Export of Permutation

coerce: % -> Array List L

Description

Coerces internal representation to an array of lists.

108aexports: Permutation 107+   (106)  107  109a
coerce: % -> Array List L;

Uses Array 599.
108bimplementation: Permutation 108b  (106)  109b
coerce(x: %): Array List L == rep x;

Uses Array 599.

Export of Permutation

coerce: % -> SetSpecies Cycle L

Description

Coerces internal representation to a set of cycles.

109aexports: Permutation 107+   (106)  108a
coerce: % -> SetSpecies Cycle L;

Uses Cycle 96 and SetSpecies 117.
109bimplementation: Permutation 108b+   (106)  108b  110a
coerce(x: %): SetSpecies Cycle L == {
import from Cycle L, SetSpecies Cycle L;
l: List Cycle L := [cycle s for s in rep x];
set l;
}

Uses Cycle 96 and SetSpecies 117.

Here we use the fact that S = E ∘C, where C is the species of cyclic permutations, i. e., we simulate the generic generation of structures as it is done in Compose. However, owing to the nature of the first and second argument of from above, it is sufficient to produce an array and not a triple as in the generic case.

110aimplementation: Permutation 108b+   (106)  109b  111a
structures(s: SetSpecies L): Generator % == generate {
import from I, Partition L;
for pi in structures(s)\$Partition(L) repeat {
arrlist := pi :: Array(List L);
for p in structures(0, arrlist) repeat yield per p;
}
}

Uses Array 599, Generator 617, I 47, Partition 146, and SetSpecies 117.

The following function is almost identical to the one given in the implementation of Compose, except that in the return type we change from SetSpecies to Array. And G is List (which represents Cycle) here.

110bimplementation: Permutation: auxiliary functions 110b  (106)
local structures(
i: I,
pi: Array List L
): Generator Array List L == generate {
import from Cycle L;
i = #pi => yield new(i)\$Array(List L);
s: SetSpecies L := set pi.i;
for g in structures(s)\$Cycle(L) repeat {
for e in structures(next i, pi) repeat {
e.i := g :: List(L);
yield e;
}
}
}

Uses Array 599, Cycle 96, Generator 617, I 47, and SetSpecies 117.

The isomorphism types of the species of permutations are, in fact, integer partitions, i. e., the same as isomorphism types of Partition.

111aimplementation: Permutation 108b+   (106)  110a  111b
isomorphismTypes(s: SetSpecies L): Generator % == generate {
import from Partition L;
for t in isomorphismTypes(s)\$Partition(L) repeat {
yield per(t :: Array(List L));
}
}

Uses Array 599, Generator 617, Partition 146, and SetSpecies 117.

The generating series is .

111bimplementation: Permutation 108b+   (106)  111a  112
generatingSeries: ExponentialGeneratingSeries == {
import from Q, DataStream Q;
stream(1) :: ExponentialGeneratingSeries;
}

Uses DataStream 386, ExponentialGeneratingSeries 316, and Q 47.

And the isomorphism type generating series is given by (192). The following code uses the right hand side of this formual.

For the workaround see ToDo 10.

112implementation: Permutation 108b+   (106)  111b  113a
local ogs(): OrdinaryGeneratingSeries == {
macro FPQ == FormalPowerSeries Q;
macro UnBug == BugWorkaround(FPQ has with {exponentiate: % -> %});
import from I, Z, Q;
local summand(n: I): Generator Q == generate {
q: Q := inv(n::Z);
yield 0; repeat {for i in 1..prev n repeat yield 0; yield q}
}
fpq: FPQ := UnBug exponentiate sum(summand(n) :: FPQ for n:I in 1..);
g: Generator Z := generate {
for c in coefficients fpq repeat {
assert(one? denominator c);
yield numerator c;
}
}
g :: OrdinaryGeneratingSeries;
}
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == ogs();

Uses BugWorkaround 48, FormalPowerSeries 242, Generator 617, I 47, OrdinaryGeneratingSeries 311, Q 47, and Z 47.

The cycle index series ZS of the species S of permutations is given by

 (11)
For the workaround see ToDo 10.
113aimplementation: Permutation 108b+   (106)  112  113b
local cis(): CycleIndexSeries == {
import from I, T, P;
m(n: I): Generator P == generate {
v: V := n::V;
n := prev n;
yield 1\$P;
for k:I in 1.. repeat {
for i:I in 1..n repeat yield 0\$P;
yield power(v, k)::P;
}
}
product(m(n) :: CycleIndexSeries for n:I in 1..);
}
cycleIndexSeries: CycleIndexSeries == cis();

Uses CycleIndexSeries 330, Generator 617, and I 47.
113bimplementation: Permutation 108b+   (106)  113a  113c
(tw: TextWriter) << (x: %): TextWriter == tw << rep x;
113cimplementation: Permutation 108b+   (106)  113b  114
(x: %) = (y: %): Boolean == rep x = rep y;
114implementation: Permutation 108b+   (106)  113c
import from String;
expression: SpeciesExpression == leaf("Permutation");

Uses Permutation 106, SpeciesExpression 430, and String 65.