#### 10.2 ExponentialGeneratingSeries

ToDo 53
rhx 44 30-Aug-2006: Move the definition at the right place in the text.

Definition 10.4 ([BLL98, p. 13]). The generating series or exponential generating series of a species of structures F is the formal power series

 (125)
where fn = cardF[U] is the number of (labelled) F-structures on a set U of n elements.

Type Constructor

Usage

f: ExponentialGeneratingSeries := monom;
s: DataStream Integer := ...
g := s :: ExponentialGeneratingSeries;

Description

Exponential generating series.

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

 (126)
316dom: ExponentialGeneratingSeries 316  (307)
ExponentialGeneratingSeries: with {
exports: ExponentialGeneratingSeries 317
} == FormalPowerSeries Fraction Integer add {
implementation: ExponentialGeneratingSeries 318b
}

Defines:
ExponentialGeneratingSeries, used in chunks 73, 86b, 93a, 101a, 111b, 124c, 128c, 132b, 142b, 160, 169a, 177–79, 184, 192a, 321a, 337, 354a, 362, 363, 628, 649, 654, 658, 705, 706, 724, 725, and 729.

Uses FormalPowerSeries 242 and Integer 66.

Exports of ExponentialGeneratingSeries

FormalPowerSeriesCategory Fraction Integer;

factorialStream: DataStream Integer Provides a stream of factorials.

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

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

317exports: ExponentialGeneratingSeries 317  (316)  318a
FormalPowerSeriesCategory Fraction Integer;

Uses FormalPowerSeriesCategory 199 and Integer 66.

Export of ExponentialGeneratingSeries

factorialStream: DataStream Integer

Description

Provides a stream of factorials.

318aexports: ExponentialGeneratingSeries 317+   (316)  317  319a
factorialStream: DataStream Integer;

Uses DataStream 386 and Integer 66.
318bimplementation: ExponentialGeneratingSeries 318b  (316)  319b
local factorial: Generator Integer == generate {
z: Integer := 1;
yield z;
yield z;
for n in 2 .. repeat {z := z * n; yield z;}
}
factorialStream: DataStream Integer == stream factorial;

Uses DataStream 386, Generator 617, and Integer 66.

Export of ExponentialGeneratingSeries

count: (%, MachineInteger) -> Integer

Description

Counts the number of structures of a given size.

319aexports: ExponentialGeneratingSeries 317+   (316)  318a  320
count: (%, MachineInteger) -> Integer;

Uses Integer 66 and MachineInteger 67.
319bimplementation: ExponentialGeneratingSeries 318b+   (316)  318b  321a
count(x: %, n: MachineInteger): Integer == {
import from DataStream Integer;
r: Fraction Integer := factorialStream n * coefficient(x, n);
assert(one? denominator r);
numerator r;
}

Uses DataStream 386, Integer 66, and MachineInteger 67.

Export of ExponentialGeneratingSeries

functorialCompose: (%, %) -> %

Description

Functorial composition of two series.

If

are two exponential generating series. Then functorialCompose(f,g) computes the functorial composite f g of the series.
 (127)
320exports: ExponentialGeneratingSeries 317+   (316)  319a
functorialCompose: (%, %) -> %;

The best guess for the approximate order of the result without accessing any coefficient is 0. So we can simply use coerce.

321aimplementation: ExponentialGeneratingSeries 318b+   (316)  319b  321b
functorialCompose(x: %, y: %): % == {
import from I, Q;
g: Generator Q := generate {
for n: I in 0..  repeat {
k: I := machine count(y, n);
yield count(x, k) / factorialStream(n);
}
}
g :: ExponentialGeneratingSeries;
}

Uses ExponentialGeneratingSeries 316, Generator 617, I 47, and Q 47.
ToDo 54
BUG! 3
mrx 8 10-Feb-2007: unfortunately, without the following chunk Axiom complains about not finding new. See also BUG 4.
321bimplementation: ExponentialGeneratingSeries 318b+   (316)  321a
#if Axiom
Rep == FormalPowerSeries Fraction Integer; import from Rep;
sum(g: Generator %): % == per sum(rep s for s in g);
#endif

Uses FormalPowerSeries 242, Generator 617, and Integer 66.