10.3 CycleIndexSeries

  10.3.1 Definitions
  10.3.2 Implementation

10.3.1 Definitions

The cycle index series ZF(x1,x2,) of a combinatorial species F is a formal power series in infinitely many variables that incorporates many properties of the species. In particular, specialization of the cycle index series gives the exponential and the ordinary generating series of a species.

F(x) = ZF(x,0,0,) (128)
˜F(x) = ZF(x,x2,x3,) (129)
Furthermore, the cycle index series is necessary to compute the type generating series of the composite of two species.

Definition 10.5. [BLL98, Def. 1.2.6] The cycle index series of a species of structures F is the formal power series (in an infinite number of variables x1,x2,x3,)

                     (                        )
                  ∑    1-∑          σ1 σ2    σn
ZF (x1,x2,x3,...) =      n!    fixF [σ]x1 x2 ...x n  ,
                  n≥0    σ∈Sn
(130)
where Sn denotes the group of permutations of [n] = {1,2,...,n}, n , and
FixF[σ] = {s ∈ F [n]|F[σ](s) = s } (131)
fixF[σ] = card(FixF[σ]) = (F[σ])1, (132)
i. e., fixF[σ] is the number of F-structures on [n] for which σ is an automorphism.

The cycle type ((F[σ])1,(F[σ])2,) of F[σ] only depends on the cycle type (σ1,n) of the permutation σ. Two permutations σ and τ have the same cycle type if and only if there exists a permutation π such that σ = π1τπ. Functoriality of F gives F[σ] = F[π]1F[τ]F[π] and proves the above statement. Thus, for j = (j1,,jn) with j1 + 2j2 + ⋅⋅⋅ + njn = n we can define fixF[j] as fixF[σ] for any permutation σ Sn with cycle type j.

Since there are anu!tj permutations of cycle type j we can rewrite (130) into

ZF(x1,x2,x3,) = n0            n
j1j=+(2jj1,2+...,⋅⋅⋅jn+)n∈jℕn=n fixF[j]  j  j
-x11x22-⋅⋅⋅xjnn-
1j1j1!⋅⋅⋅njnjn! (133)
= n0  j=(j1,...,jn)∈ℕn
j1+2j2+ ⋅⋅⋅+njn=n fixF[j] xj
autj (134)
where aut(j) is defined by (145). See Remark 1.2.10 of [BLL98].

Definition 10.6. [BLL98, App. 1, Def. 1] An action of a (multiplicative) group G on an A-weighted set (Y,w) is a function

α : G × Y → Y
(135)
such that for any g,h G, y Y (writing g y = α(g,y) to simplify notation),
  1. g (h y) = (gh) y,
  2. 1 y = y, where 1 is the unit of G,
  3. w(g y) = w(y).

Definition 10.7. [Ker91, p. 71] Let α : G × Y Y be an action of a (finite) group G on a finite set Y with n = card(Y ). The cycle index polynomial C(G,Y ;x1,,xn) [x1,,xn] is defined by

                           ∑
C (G,Y ;x1,...,xn) :=---1---   xa11...xann
                    card(G )g∈G
(136)
where φ : G SX is the (representation) homomorphism of G into the symmetric group SX that is defined by φ(g)(x) := α(g,x) and for all i = 1,2,,n ai is the number of cycles of length i of the permutation ¯g = φ(g) and .

Contrary to what one might think, the cycle index series is not the formal sum of the cycle index polynomial of the actions

αn : Sn × F [n ] → F[n], (σ,s) ↦→ αn(σ,s) = σ⋅F (s) = F[σ](s).
(137)
A cycle index polynomial corresponding to such an action would be a polynomial in card(F[n]) variables. In general we have
              ∑
ZF(x1,x2,...) ⁄=   C (Sn,F[n];x1,x2,...,xn).
              n≥0
An example is given in Chapter 1.2 of [BLL98] right after Definition 5: Consider the species F of involutions (i. e., endofunctions ψ such that ψ ψ = 1). Given U = {a,b,c,d,e}, a set of 5 elements and the permutation σ = (ab)(cde), the permutation F[σ] contains cycles of length 6. That is clearly in contradiction to the number of variables used inside the parentheses in (130) for n = 5.

The cycle index series is rather the formal sum (over all isomorphism types ˜t of F) of the cycle index polynomial of the actions

αt : Gt × [n] → [n], (σ,s) ↦→ αt(σ,s) = α(σ,s) = σ(s),
(138)
where Gt denotes the stabilizer subgroup of Sn which stabilizes t, i. e.,
G = {σ ∈ S |σt = t },
 t        n
(139)
and t F[n] is a representative of the isomorphism type ˜tF[U] (see Proposition 4.3.2 in [BLL98]).

Note that according to Definition 10.2, ˜t denotes the isomorphism type ˜t= Sn(t) T(Fn) of an element t F[n].

Similar to [BLL98, Prop. 4.3.2] we have

ZF(x1,x2,) = n0 1
--
n! σSn fixF[σ]x1σ1 xnσn
= n0 1
--
n! σSn card({s ∈ F [n]|F[σ](s) = s })x1σ1 xnσn
= n0 1
--
n! σSn sF[n][F[σ](s) = s]x1σ1 xnσn
= n0 1
--
n! sF[n] σSn[F[σ](s) = s]x1σ1 xnσn
= n0 1
--
n! sF[n] σ(Sn)sx1σ1 xnσn
= n0 1
--
n! ˜t T(Fn) card(Sn(t)) σ(Sn)tx1σ1 xnσn
= n0 tT(Fn)    1
----------
card((Sn)t) σ(Sn)tx1σ1 xnσn
= n0 ˜t T(Fn)C(Gt,[n];x1,,xn).
Note that for a predicate P(s) we used the notation
       {
         1 if P (s) is true,
[P (s)] =
         0 otherwise.
(140)

In the above derivation we relied on the Cauchy-Frobenius Theorem.

Theorem 10.8 (Cauchy-Frobenius). Let G be a finite group acting on a finite set Y then the number of orbits is the average over the number of fixed points, i.e.,

                   ∑
card(G∕Y ) =---1---    fixϕ(g),
            card(G )g∈G
(141)
where ϕ : G SY is the group homomorphism that is given by ϕ(g)(y) = g y.

10.3.2 Implementation

The main idea for the implementation of cycle index series is that it is modelled by a univariate formal power series (in x) of polynomials in infinitely many variables x1,x2, The variable x will, of course, never be considered for anything else than grouping the infinitely many power products into homogeneous polynomials of (weighted) degree n. In fact, we use equation (134).

We start by introducing a variable domain that models x1,x2, together with a weight function. Each variable xi is given the weight i. The weight is extended to powers of variables by defining the weight of xie to be ie. And the weight of a power product to be the sum of the weights of the variables (counted with multiplicity) contained in it.

Type Constructor

CycleIndexVariable

Description

Implements variables x1,x2,

This domain implements infinitely many variables indexed by positive integers where the weight of each variable is given by its index.

329dom: CycleIndexVariable 329  (307)
CycleIndexVariable: with {
        TotallyOrderedType;
        OutputType;
        coerce: MachineInteger -> %;
        weight: % -> MachineInteger;
        stretch: (%, MachineInteger) -> %;
} == add {
        Rep == MachineInteger;
        import from Rep, String;
#if Axiom
        coerce(x: %): OutputForm == sub(message "x", rep(x)::OutputForm);
#endif
        (tw: TextWriter) << (x: %): TextWriter == tw << "x" << rep x;
        coerce(i: MachineInteger): % == {
                assert(i>0); -- should throw an exception
                per i;
        }
        weight(x: %): MachineInteger == rep x;
        stretch(x: %, k: MachineInteger): % == per(rep x * k);
        compare(x: %, y: %): MachineInteger == compare(rep y, rep x);
        (x: %) < (y: %): Boolean == rep x > rep y;
        (x: %) = (y: %): Boolean == rep x = rep y;
}

Defines:
CycleIndexVariable, used in chunks 55, 307, 626, 665, 707, 709–17, 719, 721, 723, 725–27, 736a, 743, and 751c.

Uses MachineInteger 67, OutputType 570, String 65, and TotallyOrderedType 571.

Type Constructor

CycleIndexSeries

Description

Cycle index series.

CycleIndexSeries is the domain that represents cycle index series, i. e., formal power series in infinitely many variables x1,x2,x3, of the form

                 ∑
f (x1,x2,...) =           f(j1,j2,j3,...)xj11 xj22xj33 ⋅⋅⋅
             j1+2j2+⋅⋅⋅<∞
(142)
We group certain terms together and obtain
             ∑       ∑          j  j
f(x1,x2,...) =                 fjx11 x 22 ⋅⋅⋅xjnn
             n≥0 j= (j1,...,jn)∈ℕn
                j1+2j2+⋅⋅⋅+njn=n
(143)
where the polynomial under the outer sum is the sum (over all isomorphism types) of certain cycle index polynomials of degree n.

In fact, if f = ZF for some combinatorial species F then fj = fixF-[j]
autj where aut(j) is defined by (145).

If we denote by () the set of finite sequences of natural numbers then a cycle index series f is a function from () to in analogy to the fact that a formal power series (over ) is a function from to .

330dom: CycleIndexSeries 330  (307)
CycleIndexSeries: with {
        exports: CycleIndexSeries 333
} == FormalPowerSeries P add {
        Rep == FormalPowerSeries P;
        import from Rep;
        TRACE: CycleIndexSeries 332
        implementation: CycleIndexSeries 335
}

Defines:
CycleIndexSeries, used in chunks 75, 87a, 93c, 102, 113a, 125a, 129a, 133b, 143b, 163a, 169a, 177, 184, 192a, 628, 633b, 649, 654, 657, 707, 710–17, 719, 721, and 723–27.

Uses FormalPowerSeries 242.

Exports of CycleIndexSeries

FormalPowerSeriesCategory P;

coefficient: (%, T) -> Fraction Integer Coefficient of a given cycle type.

aut: T -> Integer A factor for the number of permutations of a givencycle type.

count: (%, T) -> Integer Counts the number of structures corresponding to a certain cycle type.

stretch: (%, MachineInteger) -> % Stretch a cycle index series.

compose: (%, %) -> % Composition or plethystic substitution of two cycle index series.

functorialCompose: (%, %) -> % Functorial composition of two cycle index series.

coerce: % -> OrdinaryGeneratingSeries Extract the type generating series from the cycle index series.

coerce: % -> ExponentialGeneratingSeries Extract the exponential generating series from the cycle index series.

332TRACE: CycleIndexSeries 332  (330)
import from String;
macro {
#if TRACE
        SETNAME(s)(x) == setName!(s)(x);
#else
        SETNAME(s)(x) == x;
#endif
}

Uses SETNAME 243, setName! 198, and String 65.
333exports: CycleIndexSeries 333  (330)  334
FormalPowerSeriesCategory P;

Uses FormalPowerSeriesCategory 199.

Export of CycleIndexSeries

coefficient: (%, T) -> Fraction Integer

Usage

macro {
  V == CycleIndexVariable;
  T == SparseIndexedPowerProduct(V, MachineInteger);
}
import from V, T;
s: CycleIndexSeries := ...
t: T := power(3::V,2) * power(5::V,3) * power(6::V,1);
q: Q := coefficient t;

Description

Coefficient of a given cycle type.

If for a combinatorial species F

Z  = ∑       ∑       fix F[j] xj
 F   n≥0 j=(j ,...,j )∈ℕn       autj
        j1+2j12+⋅⋅⋅+nnjn=n
(144)
and t = xj then then coefficient(s,t) returns fixaFut[jj].
334exports: CycleIndexSeries 333+   (330)  333  336
coefficient: (%, T) -> Fraction Integer;

Uses Integer 66.
335implementation: CycleIndexSeries 335  (330)  337
coefficient(x: %, t: T): Q == {
        p: P := coefficient(x, weight t);
        p(t);
}

Uses Q 47.

Export of CycleIndexSeries

aut: T -> Integer

Usage

macro {
  V == CycleIndexVariable;
  T == SparseIndexedPowerProduct(V, MachineInteger);
}
import from V, T;
t: T := power(3::V,2) * power(5::V,3) * power(6::V,1);
z: Z := aut t;

Description

A factor for the number of permutations of a givencycle type.

Given a cycle type j = (j1,j2,,jn) such that j1 + 2j2 + ⋅⋅⋅ + njn = n. Then -j1--n!jn--
1  j1!⋅⋅⋅n jn! gives the number of permutations having cycle type k. We define

aut(j) = 1j1j1!⋅⋅⋅njnjn!.
(145)
336exports: CycleIndexSeries 333+   (330)  334  338
aut: T -> Integer;

Uses Integer 66.
337implementation: CycleIndexSeries 335+   (330)  335  339
aut(t: T): Integer == {
        import from I, ExponentialGeneratingSeries, V, DataStream Z;
        z: Z := 1;
        for ev in t repeat {
                (e, v) := ev;
                w: Z := (weight v) :: Z;
                z := z * factorialStream e * w^e;
        }
        z;
}

Uses DataStream 386, ExponentialGeneratingSeries 316, I 47, Integer 66, and Z 47.

Export of CycleIndexSeries

count: (%, T) -> Integer

Usage

macro {
  V == CycleIndexVariable;
  T == SparseIndexedPowerProduct(V, MachineInteger);
}
import from V, T;
t: T := power(3::V,2) * power(5::V,3) * power(6::V,1);
z: Z := count t;

Description

Counts the number of structures corresponding to a certain cycle type.

If for a combinatorial species F

Z  = ∑       ∑       fix F[j] xj
 F   n≥0 j=(j ,...,j )∈ℕn       autj
        j1+2j12+⋅⋅⋅+nnjn=n
(146)
and t = xj then then count(s,t) returns fixF[j].
338exports: CycleIndexSeries 333+   (330)  336  340
count: (%, T) -> Integer;

Uses Integer 66.
339implementation: CycleIndexSeries 335+   (330)  337  341a
count(x: %, t: T): Integer == {
        q: Q := aut t * coefficient(x, t);
        assert(one? denominator q);
        numerator q;
}

Uses Integer 66 and Q 47.

Export of CycleIndexSeries

stretch: (%, MachineInteger) -> %

Usage

x: CycleIndexSeries := cycleIndexSeries$SetSpecies(Integer);
k: MachineInteger := 3;
s: CycleIndexSeries := stretch(x, k);

Description

Stretch a cycle index series.

For some integer k and a given cycle index series

    ∞∑
f =    fn(x1,x2,...,xn )
    n=0
the function returns a stretched series g
    ∞
g = ∑  f (x ,x  ,...,x  ).
   n=0  n k  2k     nk

Remarks

This functions respects the fact that coefficient(g,n) returns a polynomial of (weighted) degree n, i. e., the function coefficients(g) returns a sequence with gaps of size k 1 between actual non-zero polynomials.

340exports: CycleIndexSeries 333+   (330)  338  343
stretch: (%, MachineInteger) -> %;

Uses MachineInteger 67.

Let us start with some simple auxiliary functions which stretch power products and polynomials.

We keep those functions here since we see no reason why they should live in SparseIndexedPowerProduct or SparseDistributedPolynomial, since those domains are general purpose domains.

341aimplementation: CycleIndexSeries 335+   (330)  339  341b
stretch(k: I)(ev: Cross(I, V)): Cross(I, V) == {
        (e, v) := ev;
        r: Cross(I, V) := (e, stretch(v, k)$V);
}
stretch(k: I)(t: T): T == map(stretch k)(t);
stretch(k: I)(qt: Cross(Q, T)): Cross(Q, T) == {
        import from T;
        (q, t) := qt;
        qs: Cross(Q, T) := (q, map(stretch k)(t));
}

Uses I 47 and Q 47.
341bimplementation: CycleIndexSeries 335+   (330)  341a  342
local stretch(x: %, k: I)(aord: I): Generator P == generate {
        import from P, DataStream P;
        yield coefficient(x, 0); -- constant term
        gapSize: I := prev k;
        for n:I in 1.. repeat {
                for i:I in 1..gapSize repeat yield 0;
                yield map(stretch k)(coefficient(x, n));
        }
}

Uses DataStream 386, Generator 617, and I 47.
342implementation: CycleIndexSeries 335+   (330)  341b  345b
stretch(x: %, k: I): % == {
        local newApproximateOrder(): SeriesOrder == {
                zero? x => infinity;
                aox: SeriesOrder := approximateOrder x;
                assert(aox ~= unknown);
                i: I := aox :: I;
                zero? i => aox;
                (k*i) :: SeriesOrder;
        }
        SETNAME("stretch("+name(x)+")") new(stretch(x, k), newApproximateOrder);
}

Uses I 47, name 198, SeriesOrder 289, and SETNAME 243.

Export of CycleIndexSeries

compose: (%, %) -> %

Usage

x: CycleIndexSeries := cycleIndexSeries$SetSpecies(Integer);
y: CycleIndexSeries := cycleIndexSeries$NonEmpty(SetSpecies)(Integer);
z: CycleIndexSeries := compose(x, y);

Description

Composition or plethystic substitution of two cycle index series.

Let f and g be two cycle index series with g(0,0,) = 0 and let for gk denote the series given by

gk = g(xk,x2k,x3k,...),   k = 1,2,3,...
Then f g = f(g1,g2,g3,).
343exports: CycleIndexSeries 333+   (330)  340  349
compose: (%, %) -> %;

This implementation overrides the implementation of compose that is inherited by CycleIndexSeries from FormalPowerSeries.

Let us abbreviate stretch(f,k) by fk. Our implementation relies on the fact that for two series f and g we have

(f ⋅g)k = fk ⋅gk.
(147)
Now, if
f = n0  j=(j1,...,jn)∈ℕn
j1+2j2+ ⋅⋅⋅+njn=nfj x1j1 x2j2 ⋅⋅⋅xnjn
we basically compute f g as the last sum in
f g = n0  j= (j1,...,jn)∈ℕn
j1+2j2+⋅⋅⋅+njn=nfj (g1)j1 (g2)j2 ⋅⋅⋅(gn)jn (148)
= n0  j= (j1,...,jn)∈ℕn
j1+2j2+⋅⋅⋅+njn=nfj (gj1 )1 (gj2 )2⋅⋅⋅(gjn )n (149)
and the powers of g are precomputed and reused.

So let us first give an auxiliary function that computes all the powers of a given series.

345aimplementation: CycleIndexSeries: compose auxiliaries 345a  (345b)  346a
local powers(x: %): Generator % == generate {
        yield {z: % := x}
        repeat yield {z := z*x};
}

Uses Generator 617.

First of all we use the same definition as for compose from FormalPowerSeries in order to obey Convention 2. However, the first parameter is a function that is given below and quite different from the corresponding function in FormalPowerSeries.

ToDo 55
rhx 45 15-Feb-2007: See also ToDo 45 (compose).
345bimplementation: CycleIndexSeries 335+   (330)  342  350a
implementation: CycleIndexSeries: compose auxiliaries 345a
compose(x: %, y: %): % == {
        SETNAME("("+name(x)+" o "+name(y)+")")
        new(compose(x, y), *$SeriesOrder, x, y);
}

Uses name 198, SeriesOrder 289, and SETNAME 243.

The following function generates all (homogeneous) polynomials pn that appear as the summands of the outermost sum of (149). Note that a variables xi has weight i and that we take this weight into account if we speak of homogeneous polynomials.

When this function is called the third parameter gives a good guess for the resulting order of the series.

ToDo 56
rhx 46 15-Feb-2007: The code should be improved by taking care that an approximate order is already known.

if zero? aord then {
  yield coefficient(x, 0);
} else {
  for i in 0 .. prev aord repeat yield 0@P;
}

346aimplementation: CycleIndexSeries: compose auxiliaries 345a+   (345b)  345a  346b
local compose(x: %, y: %)(aord: I): Generator P == generate {
        import from P, DataStream P, DataStream %;
        TRACE("compose cis ", aord);
        assert(zero? coefficient(y, 0));
        z: % := compose(x, stream powers y);
        for p:P in elements(z :: DataStream(P)) repeat yield p;
}

Uses DataStream 386, Generator 617, and I 47.

As given above we sum over all n . For each such n there is only a polynomial with finitely many power products to consider.

346bimplementation: CycleIndexSeries: compose auxiliaries 345a+   (345b)  346a  347
local compose(x: %, yPowers: DataStream %): % == {
        import from DataStream P;
        sum(compose(p, yPowers) for p in elements(x :: DataStream(P)));
}

Uses DataStream 386.

Plethystic substitution of a polynomial p of (weighted) degree n with a power series g is done by adding all the finitely many series coming from the substitution of g into the terms of p.

ToDo 57
rhx 47 14-Feb-2007: We already know that we are homogeneous of degree n. Use that fact in sum: Array % -> %, i. e., add another parameter to allow to start the summation from index n on.
rhx 48 18-Feb-2007: Check whether

zero? p => 0;

is reasonable. We need it since the array is not allowed to be empty.
347implementation: CycleIndexSeries: compose auxiliaries 345a+   (345b)  346b  348
local compose(p: P, gPowers: DataStream %): % == {
        zero? p => 0;
        n: I := #p;
        a: Array % := new n;
        for i in 0..prev n  for c in p repeat a.i := compose(c, gPowers);
        sum a;
}

Uses Array 599, DataStream 386, and I 47.

We are left with the problem of plethystic substitution of a series g into a coefficient-power product pair. According to powers, the second parameter can be seen as (g,g2,g3,). Note, however, that the first index of a DataStream is 0.

As stated in equation (147) above, we rely on the property that stretching commutes with multiplication.

348implementation: CycleIndexSeries: compose auxiliaries 345a+   (345b)  347
local compose(c: Cross(Q, T), gPowers: DataStream %): % == {
        import from I, V, T, P;
        (q, t) := c;
        result: % := term(q :: P, 0$I);
        for ev in t repeat {
                (e, v) := ev;
                result := result * stretch(gPowers(prev e), weight v);
        }
        result;
}

Uses DataStream 386, I 47, and Q 47.

Export of CycleIndexSeries

functorialCompose: (%, %) -> %

Description

Functorial composition of two cycle index series.

Let F, G, and H be species such that H = F G. The cycle index series ZH = ZF ZG of H is defined as

ZH = n=0 1
--
n! σSn fixF[(G[σ])1,(G[σ])2,,(G[σ])lj]xσ (150)
= n0  j=(j1,...,jn)∈ℕn
j1+2j2+⋅⋅⋅+njn=n fixF[(G[j])1,(G[j])2,,(G[j])lj]  j
-x--
autj. (151)
349exports: CycleIndexSeries 333+   (330)  343  360
functorialCompose: (%, %) -> %;

Let us implement formula (151) almost literally and deal with the details later.

350aimplementation: CycleIndexSeries 335+   (330)  345b  361
implementation: CycleIndexSeries: functorial compose: auxiliaries 350b
functorialCompose(f: %, g: %): % == functorialCompose(f, g) :: %;
functorialCompose(f: %, g: %): Generator P == generate {
        import from I, Q;
        for n in 0.. repeat {
                p: P := 0;
                for s in cycleTypes n repeat {
                        t: T := cycleType(g, s);
                        q: Q := count(f, t) / aut s;
                        p := p + [q, s];
                }
                yield p;
        }
}

Uses Generator 617, I 47, and Q 47.

Looking at the definition of count(f,t), we see that for some cycle type i encoded by t = xi it returns fixF[i]. However, according to formula (151) i = ((G[j])1,(G[j])2,,(G[j])lj) for some cycle type s = xj.

Let us first deal with the problem of the generation of all cycle types of size n. It clearly corresponds to all partitions j of the integer n. We encode such a partition by a power product s = xj = x1j1xnjn and generate them via the function cycleTypes.

350bimplementation: CycleIndexSeries: functorial compose: auxiliaries 350b  (350a)  352
local cycleTypes(n: I): Generator T == integerPartitions(n, n);

Uses Generator 617 and I 47.

The generation of integer partitions is relatively simple. One just has to understand that a partition of n can start with a highest part m and the rest is an integer partition of n m that does not involve parts that are bigger than m (a bound).

Definition 10.9. An integer partition of n is tuple j = (j1,j2,,jn) such that n = k=1nk jk.

An integer partition can be used to denote the cycle type of a permutation σ Sn.

Definition 10.10. A cycle type of a permutation σ Sn is a tuple j = (j1,j2,,jn) where jk denotes the number of cycles of length k in the disjoint cycle decomposition of σ.

We usually encode a cycle type j by a power product of the form xj = x1j1x2j2⋅⋅⋅xnjn.

ToDo 58
rhx 49 11-Mar-2007: Note that the cycle types of (weighted) homogeneous degree n are generated by starting with the smallest power product so that the addition of the term in the loop over cycleTypes above is just adding to the top of the list.
mrx 9 12-Mar-2007: I guess, in the end we should use the structures as provided by a generalisation of the Partition species.
352implementation: CycleIndexSeries: functorial compose: auxiliaries 350b+   (350a)  350b  353
local integerPartitions(n: I, bound: I): Generator T == generate {
        import from V, T;
        zero? n => yield 1$T;
        m: I := min(n, bound);
        while m > 0 repeat {
                for p in integerPartitions(n-m, min(m, bound)) repeat {
                        yield p * power(m::V, 1);
                }
                m := prev m;
        }
}

Uses Generator 617 and I 47.

Next we deal with the problem of computing ((G[j])1,(G[j])2,,(G[j])lj) for some cycle type j that is encoded by s = xj. The function call cycleType(g,s) does this computation.

For the implementation of f g let us look at equation (151) more closely. We first have to figure out what lj is. Unfortunately, we cannot give a general formula for lj, since it inherently depends on the species G. An upper bound for lj is perfectly fine here, since we only need a finite value in order to stop the computation. Of course, lj cardG[n], if j = (j1,,jn) n, but cardG[n] is much too pessimistic in general. This bound is, however, quite reasonable for some species, like, for example, the species E of sets. Then cardE[n] = 1.

Let σ Sn be a permutation with cylce type j. If 1 k n, jk⁄=0 and σ is applied k times to a structure w G[n] then it is ensured that all labels in w corresponding to k-cycles in σ are back in place. The same holds if σ is applied rk times (r ). Therefore it is clear that σm w = (G[σ])m(w) = w if

m = lcm { k|1 ≤ k ≤ n,jk ⁄= 0 }.
(152)
Therefore, the longest possible cycle of G[σ] has length m.

Although the above definition of m just depends on n and j, for an upper bound for lj it makes only sense if it is known that in the functorial composition f g the series g is equal to a cycle index series ZG of some combinatorial species G. We can therefore compute lj as the minimum

l= min (cardG [n],lcm {k |1 ≤ k ≤ n,j ⁄= 0 }).
j                               k
(153)

We code the above equation into the following function where g stands for ZG and s = xj encodes the cycle index j of some permutation σ Sn.

353implementation: CycleIndexSeries: functorial compose: auxiliaries 350b+   (350a)  352  354a
local upperBoundForLongestCycle(g: %, s: T): I == {
        one? s => 1; -- s corresponds to the identity permutation
        n: I := weight s;
        a: I := card(g, n);
        b: I := cycleLengthLcm s;
        min(a, b);
}

Uses I 47.

The cardinality of G[n] is encoded in the generating series G(x) of G which we do not have available here. However, since we assume g = ZG, we can easily extract that number from the cycle index series similar to the computation of the generating series via the function coerce.

354aimplementation: CycleIndexSeries: functorial compose: auxiliaries 350b+   (350a)  353  354b
local card(g: %, n: I): I == {
        import from Q, ExponentialGeneratingSeries, DataStream Z;
        p: P := coefficient(g, n);
        zero? p => 0@I;
        (q, t) := leadingMonomial p;
        z: Z := numerator(factorialStream n * q); -- z = \card G[n]
        if z <= (max$I :: Z) then machine z else max$I; -- avoid overflow
}

Uses DataStream 386, ExponentialGeneratingSeries 316, I 47, Q 47, and Z 47.
ToDo 59
rhx 50 11-Mar-2007: The following function makes my head ache. Sooner or later I have to use Integer instead of MachineInteger in the mathematical part of Combinat. Having a MachineInteger index in DataStream is OK, but most probably not the right choice for FormalPowerSeriesCategory.
354bimplementation: CycleIndexSeries: functorial compose: auxiliaries 350b+   (350a)  354a  357
local cycleLengthLcm(s: T): I == {
        import from V, I;
        assert(not one? s);
        l: List I := [((e, v) := ev; weight v) for ev in s];
        (r, l) := (first l, rest l);
        while not empty? l repeat {
                (r, l) := (lcm(r, first l), rest l);
                assert(r>=0); -- hopefully there is no overflow
        }
        r;
}

Uses I 47.

The numbers (G[j])k that are needed in the computation of (151) can be computed using Proposition 2.2.3 of [BLL98]. For completeness, we repeat this proposition here.

Proposition 10.11. Let G be a species of structures, σ Sn, and k 1. Then the number of cycles of length k in G[σ] is given by

               (  )
(G [σ]) = 1-∑  μ  k- fixG[σd],
     k   k d|k    d
(154)
where μ denotes the Möbius function for positive integers.

For the particular case n = 0 there, we conclude that

         {
(G[σ])k =  cardG [0], if k = 1, and
          0,        for k > 1.
(155)

Note that that the cycle type i of G[σ] only depends on the cycle type j of σ.

The following function computes i = ((G[j])1,(G[j])2,,(G[j])lj) and encodes it as a power product

         (G[j])  (G[j])    (G[j])l
t = xi = x1  1x 2   2...xlj   j.
(156)
where g = ZG and s = xj. By definition of the function count, the call count(g,u) returns fixG[σd] corresponding to the formula from the proposition above.

In the following implementation we exchange the roles of d and k
d in the summand of (154).

357implementation: CycleIndexSeries: functorial compose: auxiliaries 350b+   (350a)  354b  358
local cycleType(g: %, s: T): T == BugWorkaround(
    PrimePowerProduct has with {
            divisors: % -> Generator %;
            /: (%, %) -> %;
    }
){
        import from I, Z, V, SmallIntegerTools;
        one? s => power(1::V, card(g, 0));
        t: T := 1;
        for kk in 1..upperBoundForLongestCycle(g, s) repeat {
                e: I := 0;
                k: PrimePowerProduct := factor kk;
                for d in divisors k | not zero?(m := moebiusMu(d)) repeat {
                        u: T := cycleTypePower(s, k/d);
                        e := e + m * machine count(g, u);
                }
                assert(zero?(e rem kk));
                t := power(kk::V, e quo kk) * t;
        }
        t;
}

Uses BugWorkaround 48, Generator 617, I 47, PrimePowerProduct 307, SmallIntegerTools 555, and Z 47.

The only missing part is the cycle type of σk for some permutation σ Sn with cycle type j.

According to Exercise 2.2.2 in [BLL98] we have

           ∑
(σk)m =           dσdm.
            d|k
        gcd(m,k∕d)=1
(157)
In the following function we iterate this formula for 0 m n and encode in the result u the cycle type of σk.
358implementation: CycleIndexSeries: functorial compose: auxiliaries 350b+   (350a)  357  359a
local cycleTypePower(s: T, k: PrimePowerProduct): T == BugWorkaround(
    PrimePowerProduct has with {
            divisors: % -> Generator %;
            /: (%, %) -> %;
    }
) BugWorkaround(T has with {apply: (%, V) -> I}){
        import from V;
        u: T := 1; -- cycle type of sigma^k where cycletype(sigma)=s
        n: I := weight s;
        for m in 1..n repeat {
                e: I := 0;
                for d in divisors k | trivialGcd?(m, k/d) repeat {
                        a: I := multiply d; -- multiply out prime power product
                        e := e + a * s((a*m)::V);
                }
                u := power(m::V, e) * u;
        }
        u;
}

Uses BugWorkaround 48, Generator 617, I 47, and PrimePowerProduct 307.

In the above code we use two auxiliary functions. The first one returns true if and only if gcd(i,k) = 1.

359aimplementation: CycleIndexSeries: functorial compose: auxiliaries 350b+   (350a)  358  359b
local trivialGcd?(i: I, k: PrimePowerProduct): Boolean == {
        for ep in k repeat {
                (e, p) := ep;
                zero?(i rem p) => return false;
        }
        true;
}

Uses I 47 and PrimePowerProduct 307.

The second function simply multiplies all the prime powers contained in k.

359bimplementation: CycleIndexSeries: functorial compose: auxiliaries 350b+   (350a)  359a
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.

Export of CycleIndexSeries

coerce: % -> OrdinaryGeneratingSeries

Description

Extract the type generating series from the cycle index series.

According to Theorem 8 in [BLL98], we have for a species F

˜F (x) = ZF(x,x2,x3,x4,...)
(158)
for the type generating series ˜F(x) given the cycle index series ZF of the species.
360exports: CycleIndexSeries 333+   (330)  349  362
coerce: % -> OrdinaryGeneratingSeries;

Uses OrdinaryGeneratingSeries 311.

According to (158) we basically have to replace all variables xi by xi. We have grouped the cycle index series into homogeneous polynomials pn. The substitution (158) and extraction of the coefficient of xn amounts to summing the coefficients of all power products of the polynomial pn.

361implementation: CycleIndexSeries 335+   (330)  350a  363
typeGeneratingSeriesCoefficients(f: %)(aord: I): Generator Z == generate {
        import from Z, Q, T, P, DataStream P;
        TRACE("typeGeneratingSeriesCoefficients ", "BEGIN");
        for n: I in 1..aord repeat yield 0@Z;
        for p in elements(f :: DataStream P, aord) repeat {
                q: Q := 0;
                for ct in p repeat {
                        (c, t) := ct;
                        q := q + c;
                }
                assert(one? denominator q);
                yield numerator q;
        }
}
coerce(f: %): OrdinaryGeneratingSeries == SETNAME("OGS("+name(f)+")") new(
    typeGeneratingSeriesCoefficients f,
    (): SeriesOrder +-> approximateOrder(f)
);

Uses DataStream 386, Generator 617, I 47, name 198, OrdinaryGeneratingSeries 311, Q 47, SeriesOrder 289, SETNAME 243, and Z 47.

Export of CycleIndexSeries

coerce: % -> ExponentialGeneratingSeries

Description

Extract the exponential generating series from the cycle index series.

According to Theorem 8 in [BLL98], we have for a species F

F(x) = ZF (x,0,0,0,...)
(159)
for the exponential generating series F(x) given the cycle index series ZF of the species.
362exports: CycleIndexSeries 333+   (330)  360
coerce: % -> ExponentialGeneratingSeries;

Uses ExponentialGeneratingSeries 316.

According to (159) we only need to extract the term that solely involves the variable x1. We have grouped the cycle index series into homogeneous polynomials pn. The order on the terms (type T) that we have imposed on in type P is such that it suffices to take the leading coefficient of the pn as long as it is not zero. If pn⁄=0 then it must contain the power product x1n, since its coefficient corresponds to the number of structures of size n. We simply extract that coefficient and form a new series.

363implementation: CycleIndexSeries 335+   (330)  361  364
generatingSeriesCoefficients(f: %)(aord: I): Generator Q == generate {
        import from I, Q, V, T, P, DataStream P;
        for n: I in 1..aord repeat yield 0@Q;
        for p in elements(f :: DataStream P, aord) repeat {
                zero? p => yield 0@Q;
                (q, t) := leadingMonomial p;
                assert(
                    import from Boolean;
                    l: List Cross(I, V) := [generator t];
                    empty? l => true; -- t=1
                    not empty? rest l => false; -- more than 1 variables
                    (e, v) := first l;
                    one? weight v;
                );
                yield q;
        }
}
coerce(f: %): ExponentialGeneratingSeries == SETNAME("EGS("+name(f)+")") new(
    generatingSeriesCoefficients f,
    (): SeriesOrder +-> approximateOrder(f)
);

Uses DataStream 386, ExponentialGeneratingSeries 316, Generator 617, I 47, name 198, Q 47, SeriesOrder 289, and SETNAME 243.
ToDo 60
BUG! 4
mrx 10 10-Feb-2007: unfortunately, without the following chunk Axiom complains:
coefficient(cycleIndexSeries()$Partition ACINT, 4)  
Looking in PrimitiveArray(FormalPowerSeries(  
               SparseDistributedPolynomial(  
                   ACFraction(ACInteger()),  
                   CycleIndexVariable(),  
                   SparseIndexedPowerProduct(CycleIndexVariable(),  
                                             ACMachineInteger()))))  
for new with code 937065024  
 
>> System error:  
FOAM-USER::|fiRaiseException| is invalid as a function.  
    

364implementation: CycleIndexSeries 335+   (330)  363
#if Axiom
sum(g: Generator %): % == per sum(rep s for s in g);
#endif

Uses Generator 617.