24.12 Test Composition
Here we check whether S = E ∘C.
649⟨test 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+++….
650⟨test 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():
-
-
B := taylor(zerosOf(-b+x+b^2, b).2,x=0)
elt(B, taylor(x/(1-x), x=0))
652⟨test 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.
654⟨test 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.