#### 8.12 Composition of Species

Definition 8.13. [BLL98, chp. 1.4] Let F and G be two species of structures such that G[] = (i. e., there is no G-structure on the empty set). The species F G (also denoted F(G)), called the (partitional) composite of F with G, is defined as

 (45)
for any finite set U where the (disjoint) sum is taken over the set of partitions π of U (i. e., π Par[U]).
ToDo 30
rhx 19 28-Sep-2006: Add transport condition due to [BLL98, chp. 1.4].

Type Constructor

Description

Composition of combinatorial species.

Compose(
F: SPECIES,
G: SPECIES
)(L: LabelType): CombinatorialSpecies(L) == add {
Rep == Record(
tag: Partition L,
left: F SetSpecies L,
right: SetSpecies G L
);
import from Rep;
implementation: Compose: auxiliary functions 186
implementation: Compose 182b
}

Defines:
Compose, used in chunks 442, 455, 649, 650, 652, 654, 719, 721, and 723.

Uses CombinatorialSpecies 71, LabelType 62, Partition 146, SetSpecies 117, and SPECIES 55.
182bimplementation: Compose 182b  (182a)  183
(tw: TextWriter) << (x: %): TextWriter == {
import from String;
tw << "(" << rep(x).left << ", " << rep(x).right << ")";
}

Uses String 65.
183implementation: Compose 182b+   (182a)  182b  184
(x: %) = (y: %): Boolean == {
macro {X == rep x; Y == rep y}
(X.tag = Y.tag) and (X.left = Y.left) and (X.right = Y.right);
}

The generating series corresponding to the composition of the species F and G are:

 (F ∘ G)(x) = F(G(x)), (46) = ZF((x),(x2),(x3)…) (47) ZF∘G(x1,x2,…) = ZF(ZG(x1,x2,…),ZG(x2,x4,…),…). (48)
ToDo 31
rhx 20 16-Mar-2007: We should rather really implement (47) instead of computing ZFG and only then substitute xi by xi.
184implementation: Compose 182b+   (182a)  183  185a
generatingSeries: ExponentialGeneratingSeries == new();
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == new();
cycleIndexSeries: CycleIndexSeries == new();
expression: SpeciesExpression == new();
local init(): () == {
set!(
generatingSeries \$ %,
compose(generatingSeries \$ F(L), generatingSeries \$ G(L))
);
set!(
cycleIndexSeries \$ %,
compose(cycleIndexSeries \$ F(L), cycleIndexSeries \$ G(L))
);
set!(
isomorphismTypeGeneratingSeries \$ %,
(cycleIndexSeries \$ %) :: OrdinaryGeneratingSeries
);
set!(expression\$%, compose(expression\$F(L), expression\$G(L)));
}
init();

Uses CycleIndexSeries 330, ExponentialGeneratingSeries 316, OrdinaryGeneratingSeries 311, and SpeciesExpression 430.
ToDo 32
rhx 21 28-Sep-2006: Check that G[] = .
According to (45), we must sum (generate) over all partitions of the input set.
185aimplementation: Compose 182b+   (182a)  184  188a
structures(s: SetSpecies L): Generator % == generate {
for pi in structures(s)\$Partition(L) repeat {
Yield elements of F[π] × pπ G[p] 185b
}
}

Uses Generator 617, Partition 146, and SetSpecies 117.
185bYield elements of F[π] × pπ G[p] 185b  (185a)
import from MachineInteger, Partition L;
arrlist: Array List L := pi::Array List L;
for f in structures(pi::SetSpecies(SetSpecies L))\$F(SetSpecies L) repeat {
for p in structures(0, arrlist) repeat yield per [pi, f, p];
}

Uses Array 599, MachineInteger 67, Partition 146, and SetSpecies 117.

As an auxiliary function, we compute pπG[p] recursively. The following function yields the elements of this set in a lexicographic order according to the order of the sets in the partition π.

186implementation: Compose: auxiliary functions 186  (182a)  189
local structures(
i: I,
pi: Array List L
): Generator SetSpecies G L == generate {
import from SetSpecies G L, List G L;
i = #pi => yield empty\$SetSpecies(G L);
s: SetSpecies L := set pi.i;
for g in structures(s)\$G(L) repeat {
for e in structures(next i, pi) repeat yield cons(g, e);
}
}

Uses Array 599, Generator 617, I 47, and SetSpecies 117.
ToDo 33
mrx 5 It is very unlikely that there is a good algorithm to unrank a composition of two species in general. See the email of Nicolas Thiery,

However, we can generate all as follows:

1. generate the isomorphism types of Partition.
2. for a set partition π, regarded as a set of sets, generate the isomorphism types of F[π].
3. for all different blocksizes s in π, generate all the of G[1,2,,s], and select a multiset with size being the multiplicity of s in π.
rhx 22 25-Mar-2007: My idea would rather be to replace the line

isomorphismTypes(pi::SetSpecies(SetSpecies L))\$F(SetSpecies L)

below by

isomorphismTypes(pi)\$F(L)

By that we basically consider the representative pi as a true partition structure and then let F decide in how many different ways pi can contribute non-isomorphic structures. Since the results are again representatives, we simply ask for all the isomorphism types of G in a similar was as we do for structures.

Although that approach would require each domain that appears as the first argument of Compose to provide an additional function

isomorphismTypes: Partition L -> Generator %

I believe that this can relatively easily be achieved and it would allow to produce representatives of isomorphism types of Compose.

In fact, using Partition instead of SetSpecies is basically encoding a multiset.

188aimplementation: Compose 182b+   (182a)  185a
isomorphismTypes(s: SetSpecies L): Generator % == generate {
TRACE("iso enter s=", s);
for pi in isomorphismTypes(s)\$Partition(L) repeat {
iso: Yield elements of F[π] × pπ G[p] 188b
}
}

Uses Generator 617, Partition 146, and SetSpecies 117.
188biso: Yield elements of F[π] × pπ G[p] 188b  (188a)
import from MachineInteger, Partition L;
arrlist: Array List L := pi::Array List L;
for f in isomorphismTypes(pi::SetSpecies(SetSpecies L))\$F(SetSpecies L) repeat {
for p in isomorphismTypes(0, arrlist) repeat {
yield per [pi, f, p];
}
}

Uses Array 599, MachineInteger 67, Partition 146, and SetSpecies 117.

As an auxiliary function, we compute pπG[p] recursively. The following function yields the elements of this set in a lexicographic order according to the order of the sets in the partition π.

189implementation: Compose: auxiliary functions 186+   (182a)  186
local isomorphismTypes(
i: I,
pi: Array List L
): Generator SetSpecies G L == generate {
import from SetSpecies G L, List G L;
TRACE("iso #pi=", i);
import from List L; -- TRACE
TRACE("iso pi=", pi);
i = #pi => yield empty\$SetSpecies(G L);
s: SetSpecies L := set pi.i;
for g in isomorphismTypes(s)\$G(L) repeat {
for e in isomorphismTypes(next i, pi) repeat yield cons(g, e);
}
}

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