ExponentialGeneratingSeries

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 f_n = cardF[U] is the number of (labelled) F-structures on a set U of n elements.

Type Constructor

ExponentialGeneratingSeries

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)

316⟨dom: 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.

317⟨exports: 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.

318a⟨exports: ExponentialGeneratingSeries 317⟩+≡ (316) ⊲317 319a ⊳
factorialStream: DataStream Integer;

Uses DataStream 386 and Integer 66.

318b⟨implementation: 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.

319a⟨exports: ExponentialGeneratingSeries 317⟩+≡ (316) ⊲318a 320 ⊳
count: (%, MachineInteger) -> Integer;

Uses Integer 66 and MachineInteger 67.

319b⟨implementation: 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.

∞∑ xn ∞∑ xn
f = fnn!- and g = gnn!-
n=0 n=0

are two exponential generating series . Then functorialCompose(f,g) computes the functorial composite f ⊓ ⊔ g of the series.

(127)

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

321a⟨implementation: 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.

321b⟨implementation: 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.

10.2 ExponentialGeneratingSeries