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

(F ∘G )[U] =    ∑       F[π]× ∏  G[p]
           π partition of U     p∈π
(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

Compose

Description

Composition of combinatorial species.

182adom: Compose 182a  (55)
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)
(F ∘ G) = ZF(G˜(x),G˜(x2),˜G(x3)) (47)
ZFG(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,

http://www.mail-archive.com/aldor-combinat-devel%40lists.sourceforge.net/msg00133.html.

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.