24.12 Test Composition

Here we check whether S = E ∘C.

649test Compose 649  (626)  650
testCycleAndPermutation(): () == {
        macro {
                CS == CombinatorialSpecies;
                E == SetSpecies;
                C == Cycle;
                S == Permutation(Z);
        }
        EC(L: LabelType): CS L == Compose(E, C)(L) add;
        import from Integer, Array Integer, Array P;
        egs: ExponentialGeneratingSeries := generatingSeries $ S;
        ogs: OrdinaryGeneratingSeries := isomorphismTypeGeneratingSeries $ S;
        cis: CycleIndexSeries := cycleIndexSeries $ S;
        check(
            EC,
            [count(egs, n) for n:I in 0..10],
            [coefficient(ogs, n) for n:I in 0..10],
            [coefficient(cis, n) for n:I in 0..10]
        );
}

Uses Array 599, CombinatorialSpecies 71, Compose 182a, Cycle 96, CycleIndexSeries 330, ExponentialGeneratingSeries 316, I 47, Integer 66, LabelType 62, OrdinaryGeneratingSeries 311, Permutation 106, SetSpecies 117, and Z 47.

We can construct binary forests as sets of binary trees. The generatingSeries is simply the exponential of the generatingSeries of binary trees.

The first few terms of the isomorphismTypeGeneratingSeries can be derived in Axiom as follows:

B := taylor(zerosOf(-b + x + b^2, b).2, x=0)
X := monomial(1,1)$UnivariateTaylorSeries(Expression Integer, x, 0)
exp(B+elt(B, X^2)/2+elt(B, X^3)/3)

since the cycleIndicatorSeries of SetSpecies equals ex1+x2
 2+x3
 3+.
650test Compose 649+   (626)  649  652
testBinaryForests(): () == {
        macro {
                CS == CombinatorialSpecies;
                X == SingletonSpecies;
        }
        B(L: LabelType): CS L == Plus(X, Times(B,B))(L) add;
        F(L: LabelType): CS L == Compose(SetSpecies, B)(L) add;
        import from Integer, Array Integer;
        check(
            F,
            [1,1,3,19,193,2721,49171,1084483,28245729,848456353],
            [1,1,2,4,10,26,77,235,758,2504],
[
                1,
                x(1),
                (3/2)*x(1,2)+(inv 2)*x(2),

                (19/6)*x(1,3)+(inv 2)*x(1)*x(2)+(inv 3)*x(3),

                (193/24)*x(1,4)+(3/4)*x(1,2)*x(2)+(inv 3)*x(1)*x(3)
                +(5/8)*x(2,2)+(inv 4)*x(4),

                (907/40)*x(1,5)+(19/12)*x(1,3)*x(2)+(inv 2)*x(1,2)*x(3)
                +(5/8)*x(1)*x(2,2)+(inv 4)*x(1)*x(4)+(inv 6)*x(2)*x(3)
                +(inv 5)*x(5),

                (49171/720)*x(1,6)+(193/48)*x(1,4)*x(2)+(19/18)*x(1,3)*x(3)
                +(15/16)*x(1,2)*x(2,2)+(3/8)*x(1,2)*x(4)
                +(inv 6)*x(1)*x(2)*x(3)+(inv 5)*x(1)*x(5)+(61/48)*x(2,3)
                +(inv 8)*x(2)*x(4)+(7/18)*x(3,2)+(inv 6)*x(6),

                (1084483/5040)*x(1,7)+(907/80)*x(1,5)*x(2)
                +(193/72)*x(1,4)*x(3)+(95/48)*x(1,3)*x(2,2)
                +(19/24)*x(1,3)*x(4)+(inv 4)*x(1,2)*x(2)*x(3)
                +(3/10)*x(1,2)*x(5)+(61/48)*x(1)*x(2,3)
                +(inv 8)*x(1)*x(2)*x(4)+(7/18)*x(1)*x(3,2)
                +(inv 6)*x(1)*x(6)+(5/24)*x(2,2)*x(3)+(inv 10)*x(2)*x(5)
                +(inv 12)*x(3)*x(4)+(inv 7)*x(7),

                (9415243/13440)*x(1,8)+(49171/1440)*x(1,6)*x(2)
                +(907/120)*x(1,5)*x(3)+(965/192)*x(1,4)*x(2,2)
                +(193/96)*x(1,4)*x(4)+(19/36)*x(1,3)*x(2)*x(3)
                +(19/30)*x(1,3)*x(5)+(61/32)*x(1,2)*x(2,3)
                +(3/16)*x(1,2)*x(2)*x(4)+(7/12)*x(1,2)*x(3,2)
                +(inv 4)*x(1,2)*x(6)+(5/24)*x(1)*x(2,2)*x(3)
                +(inv 10)*x(1)*x(2)*x(5)+(inv 12)*x(1)*x(3)*x(4)
                +(inv 7)*x(1)*x(7)+(1225/384)*x(2,4)+(5/32)*x(2,2)*x(4)
                +(7/36)*x(2)*x(3,2)+(inv 12)*x(2)*x(6)+(inv 15)*x(3)*x(5)
                +(9/32)*x(4,2)+(inv 8)*x(8),

                (848456353/362880)*x(1,9)+(1084483/10080)*x(1,7)*x(2)
                +(49171/2160)*x(1,6)*x(3)+(907/64)*x(1,5)*x(2,2)
                +(907/160)*x(1,5)*x(4)+(193/144)*x(1,4)*x(2)*x(3)
                +(193/120)*x(1,4)*x(5)+(1159/288)*x(1,3)*x(2,3)
                +(19/48)*x(1,3)*x(2)*x(4)+(133/108)*x(1,3)*x(3,2)
                +(19/36)*x(1,3)*x(6)+(5/16)*x(1,2)*x(2,2)*x(3)
                +(3/20)*x(1,2)*x(2)*x(5)+(inv 8)*x(1,2)*x(3)*x(4)
                +(3/14)*x(1,2)*x(7)+(1225/384)*x(1)*x(2,4)
                +(5/32)*x(1)*x(2,2)*x(4)+(7/36)*x(1)*x(2)*x(3,2)
                +(inv 12)*x(1)*x(2)*x(6)+(inv 15)*x(1)*x(3)*x(5)
                +(9/32)*x(1)*x(4,2)+(inv 8)*x(1)*x(8)+(61/144)*x(2,3)*x(3)
                +(inv 8)*x(2,2)*x(5)+(inv 24)*x(2)*x(3)*x(4)
                +(inv 14)*x(2)*x(7)+(127/162)*x(3,3)+(inv 18)*x(3)*x(6)
                +(inv 20)*x(4)*x(5)+(inv 9)*x(9)
            ]
        );
}

Uses Array 599, CombinatorialSpecies 71, Compose 182a, Integer 66, LabelType 62, Plus 166a, SetSpecies 117, SingletonSpecies 84, and Times 175a.

Similarly, we can construct binary forests of nonempty sets. The generatingSeries is the generatingSeries of binary trees B, composed with the exponential minus one:

B := taylor(zerosOf(-b+x+b^2, b).2,x=0)
elt(B, taylor(exp x-1, x=0))

Since the cycle indicator series of binary forests is B(x1), the isomorphismTypeGeneratingSeries is B(-x-
1−x):

B := taylor(zerosOf(-b+x+b^2, b).2,x=0)
elt(B, taylor(x/(1-x), x=0))

652test Compose 649+   (626)  650  654
testBinaryTreesOfSets(): () == {
        macro {
                CS == CombinatorialSpecies;
                X == SingletonSpecies;
        }

        B(L: LabelType): CS L == Plus(X, Times(B,B))(L) add;
        F(L: LabelType): CS L == Compose(B, NonEmpty SetSpecies)(L) add;

        import from Integer, Array Integer;
        check(
            F,
            [0,1,3,19,207,3211,64383,1581259,45948927,1541641771],
            [0,1,2,5,15,51,188,731,2950,12235],
            [
                0,
                x(1),
                (3/2)*x(1,2)+(inv 2)*x(2),
                (19/6)*x(1,3)+(3/2)*x(1)*x(2)+(inv 3)*x(3),

                (69/8)*x(1,4)+(19/4)*x(1,2)*x(2)+x(1)*x(3)+(3/8)*x(2,2)
                +(inv 4)*x(4),

                (3211/120)*x(1,5)+(69/4)*x(1,3)*x(2)+(19/6)*x(1,2)*x(3)
                +(19/8)*x(1)*x(2,2)+(3/4)*x(1)*x(4)+(inv 2)*x(2)*x(3)
                +(inv 5)*x(5),

                (21461/240)*x(1,6)+(3211/48)*x(1,4)*x(2)+(23/2)*x(1,3)*x(3)
                +(207/16)*x(1,2)*x(2,2)+(19/8)*x(1,2)*x(4)
                +(19/6)*x(1)*x(2)*x(3)+(3/5)*x(1)*x(5)+(19/48)*x(2,3)
                +(3/8)*x(2)*x(4)+(inv 6)*x(3,2)+(inv 6)*x(6),

                (1581259/5040)*x(1,7)+(21461/80)*x(1,5)*x(2)
                +(3211/72)*x(1,4)*x(3)+(3211/48)*x(1,3)*x(2,2)
                +(69/8)*x(1,3)*x(4)+(69/4)*x(1,2)*x(2)*x(3)
                +(19/10)*x(1,2)*x(5)+(69/16)*x(1)*x(2,3)+(19/8)*x(1)*x(2)*x(4)
                +(19/18)*x(1)*x(3,2)+(inv 2)*x(1)*x(6)+(19/24)*x(2,2)*x(3)
                +(3/10)*x(2)*x(5)+(inv 4)*x(3)*x(4)+(inv 7)*x(7),

                (15316309/13440)*x(1,8)+(1581259/1440)*x(1,6)*x(2)
                +(21461/120)*x(1,5)*x(3)+(21461/64)*x(1,4)*x(2,2)
                +(3211/96)*x(1,4)*x(4)+(3211/36)*x(1,3)*x(2)*x(3)
                +(69/10)*x(1,3)*x(5)+(3211/96)*x(1,2)*x(2,3)
                +(207/16)*x(1,2)*x(2)*x(4)+(23/4)*x(1,2)*x(3,2)
                +(19/12)*x(1,2)*x(6)+(69/8)*x(1)*x(2,2)*x(3)
                +(19/10)*x(1)*x(2)*x(5)+(19/12)*x(1)*x(3)*x(4)
                +(3/7)*x(1)*x(7)+(69/128)*x(2,4)+(19/32)*x(2,2)*x(4)
                +(19/36)*x(2)*x(3,2)+(inv 4)*x(2)*x(6)
                +(inv 5)*x(3)*x(5)+(3/32)*x(4,2)+(inv 8)*x(8),

                (1541641771/362880)*x(1,9)+(15316309/3360)*x(1,7)*x(2)
                +(1581259/2160)*x(1,6)*x(3)+(1581259/960)*x(1,5)*x(2,2)
                +(21461/160)*x(1,5)*x(4)+(21461/48)*x(1,4)*x(2)*x(3)
                +(3211/120)*x(1,4)*x(5)+(21461/96)*x(1,3)*x(2,3)
                +(3211/48)*x(1,3)*x(2)*x(4)+(3211/108)*x(1,3)*x(3,2)
                +(23/4)*x(1,3)*x(6)+(3211/48)*x(1,2)*x(2,2)*x(3)
                +(207/20)*x(1,2)*x(2)*x(5)+(69/8)*x(1,2)*x(3)*x(4)
                +(19/14)*x(1,2)*x(7)+(3211/384)*x(1)*x(2,4)
                +(207/32)*x(1)*x(2,2)*x(4)+(23/4)*x(1)*x(2)*x(3,2)
                +(19/12)*x(1)*x(2)*x(6)+(19/15)*x(1)*x(3)*x(5)
                +(19/32)*x(1)*x(4,2)+(3/8)*x(1)*x(8)+(23/16)*x(2,3)*x(3)
                +(19/40)*x(2,2)*x(5)+(19/24)*x(2)*x(3)*x(4)+(3/14)*x(2)*x(7)
                +(19/162)*x(3,3)+(inv 6)*x(3)*x(6)+(3/20)*x(4)*x(5)
                +(inv 9)*x(9)
            ]
        );
}

Uses Array 599, CombinatorialSpecies 71, Compose 182a, Integer 66, LabelType 62, NonEmpty 131a, Plus 166a, SetSpecies 117, SingletonSpecies 84, and Times 175a.

The following code tests the definition of NonEmptySetSpecies via restriction and the definition of Partition via the combinatorial equality Par = E E1.

654test Compose 649+   (626)  652
testPartitionsViaCompose(): () == {
        macro S == Partition Integer;
        MyPartition(L: LabelType): CombinatorialSpecies L == {
                Compose(SetSpecies, NonEmpty SetSpecies)(L) add;
        }

        egs: ExponentialGeneratingSeries == generatingSeries $ S;
        ogs: OrdinaryGeneratingSeries == isomorphismTypeGeneratingSeries $ S;
        cis: CycleIndexSeries == cycleIndexSeries $ S;

        import from Integer, Array Integer;
        check(
            MyPartition,
            [count(egs, n) for n: I in 0..9],
            [coefficient(ogs, n) for n: I in 0..9],
            [coefficient(cis, n) for n: I in 0..9]
        );
}

Uses Array 599, CombinatorialSpecies 71, Compose 182a, CycleIndexSeries 330, ExponentialGeneratingSeries 316, I 47, Integer 66, LabelType 62, NonEmpty 131a, OrdinaryGeneratingSeries 311, Partition 146, and SetSpecies 117.