10.1 OrdinaryGeneratingSeries

ToDo 51
rhx 43 10-Jan-2007: Move definition of isomorphism type to the right place.

Definition 10.1. [BLL98, Def. 1.1.4] Consider two F-structures s1 F[U] and s2 F[V ]. A bijection σ : U V is called an isomorphism of s1 to s2 if s2 = σs1 = F[σ](s1). One says that these structures have the same isomorphism type. Moreover, an isomorphism from s to s is said to be an automorphism of s.

Definition 10.2. [BLL98, p. 14] Let U be a set. We define an equivalence relation on F[U] by setting for s,t F[U]

s t if and only if s and t have the same isomorphism type.

In other words, s t if and only if there exists a permutation π : U U such that F[π](s) = t. By ˜s we denote the isomorphism type of s.

Let us furthermore define

T(Fn) = F[n] (120)
T(F) = n0T(Fn). (121)

Note that ˜t= Sn(t) is also know as the orbit of t with respect to the action

α : Sn × F [n] → F[n], (σ,s) ↦→ F [σ ](s)
of the symmetric group Sn on F[n].

Definition 10.3. [BLL98, p. 15] The (isomorphism) type generating series or ordinary generating series of a species of structures F is the formal power series

˜F(x) = ∑ f˜xn
      n=0 n
where f˜n = card(T(Fn)) is the number of (unlabelled) F-structures on a set U of n elements.

Type Constructor



f: OrdinaryGeneratingSeries := monom;


Ordinary generating series.

OrdinaryGeneratingSeries is the domain that represents ordinary generating series, i. e., formal power series f of the form

    ∞∑     n
f =    fnx .
311dom: OrdinaryGeneratingSeries 311  (307)
OrdinaryGeneratingSeries: with {
        exports: OrdinaryGeneratingSeries 312
} == FormalPowerSeries Integer add {
        implementation: OrdinaryGeneratingSeries 313b

OrdinaryGeneratingSeries, used in chunks 74, 86c, 93b, 101b, 112, 124d, 128d, 133a, 143a, 162, 169a, 177, 184, 192a, 360, 361, 628, 649, 654, 724, 725, and 729.

Uses FormalPowerSeries 242 and Integer 66.

Exports of OrdinaryGeneratingSeries

FormalPowerSeriesCategory Integer;

count: (%, MachineInteger) -> Integer Counts the number of structures of a given size.

312exports: OrdinaryGeneratingSeries 312  (311)  313a
FormalPowerSeriesCategory Integer;

Uses FormalPowerSeriesCategory 199 and Integer 66.

Export of OrdinaryGeneratingSeries

count: (%, MachineInteger) -> Integer


Counts the number of structures of a given size.

313aexports: OrdinaryGeneratingSeries 312+   (311)  312
count: (%, MachineInteger) -> Integer;

Uses Integer 66 and MachineInteger 67.
313bimplementation: OrdinaryGeneratingSeries 313b  (311)  314
count(x: %, n: MachineInteger): Integer == coefficient(x, n);

Uses Integer 66 and MachineInteger 67.
ToDo 52
BUG! 2
mrx 7 10-Feb-2007: unfortunately, without the following chunk Axiom complains about not finding new. See also BUG 4.
314implementation: OrdinaryGeneratingSeries 313b+   (311)  313b
#if Axiom
Rep == FormalPowerSeries Integer; import from Rep;
sum(g: Generator %): % == per sum(rep s for s in g);

Uses FormalPowerSeries 242, Generator 617, and Integer 66.