8.9 Partition Species

  8.9.1 Restricted Growth Functions
  8.9.2 Generating Set Partitions
  8.9.3 Generating Integer Partitions
  8.9.4 The Number of Set Partitions
  8.9.5 The Number of Integer Partitions

Definition 8.7. A set partition of a set X is an collection X ⊂P(X) of subsets of X such that X = X and Y Z = for any Y,Z ∈X with Y ⁄=Z. X is called a set partition into m parts if cardX = m.

As given in [BLL98, Chp. 1.4], set partitions Par can be obtained by the combinatorial equation

Par = E(E+)
(20)
where E is the set species and E+ is the species of non-empty sets.

However, looking closer at the definition of composition F G of two species F and G, (cf. (45)) one sees that set partitions are needed. Thus we decided to implement the species Partition as a basic species.

Type Constructor

Partition

Description

Species of Partitions.

The structures of this species are set partitions. Its isomorphism types are the integer partitions.

146dom: Partition 146  (55)
Partition(L: LabelType): with {
        exports: Partition 147a
} == add {
        representation: Partition 147b
        import from Rep;
        implementation: Partition: auxiliary functions 159
        implementation: Partition 148b
}

Defines:
Partition, used in chunks 110a, 111a, 164, 182a, 185, 188, 455, 634, 654, 661a, 665, and 716.

Uses LabelType 62.

Exports of Partition

CombinatorialSpecies L;

coerce: % -> Array List L Coerces internal representation to an array of lists.

coerce: % -> SetSpecies SetSpecies L Coerces internal representation to a set of sets.

restrictedGrowthArrays: MachineInteger -> Generator PrimitiveArray MachineInteger Generates restricted growth arrays of a given size.

Clearly, we want set partitions to be a combinatorial species.

147aexports: Partition 147a  (146)  148a
CombinatorialSpecies L;

Uses CombinatorialSpecies 71.

We have decided for an array of lists as the representation since it was easier to implement the isomorphism between restricted growth functions and set partitions using an array than a list.

147brepresentation: Partition 147b  (146)
Rep == Array List L;

Uses Array 599.

Export of Partition

coerce: % -> Array List L

Description

Coerces internal representation to an array of lists.

148aexports: Partition 147a+   (146)  147a  149a
coerce: % -> Array List L;

Uses Array 599.
148bimplementation: Partition 148b  (146)  149b
coerce(x: %): Array List L == rep x;

Uses Array 599.

Export of Partition

coerce: % -> SetSpecies SetSpecies L

Description

Coerces internal representation to a set of sets.

149aexports: Partition 147a+   (146)  148a  153
coerce: % -> SetSpecies SetSpecies L;

Uses SetSpecies 117.
149bimplementation: Partition 148b+   (146)  148b  155a
coerce(x: %): SetSpecies SetSpecies L == {
    import from SetSpecies L;
    l: List SetSpecies L := [set s for s in rep x];
    set l;
}

Uses SetSpecies 117.
8.9.1 Restricted Growth Functions

In order to generate set partitions it is easier to generate restricted growth functions and then use an easy bijection to get the actual set partition.

Definition 8.8. [KS98] A restricted growth function of length n > 0 is a function

f : {0,...,n− 1} → ℕ
which satisfies the following conditions:
f(0) = 0 (21)
f(i) 1 + max{f(0),...,f(i− 1)}, if 1 i < n. (22)

The bijection σ which maps restricted growth functions of length n to set partitions of X = {0,...,n− 1} is given below.

Let f be a restricted growth function of length n and

m = max {f(0),...,f(n− 1)}
then σ(f) = {X0, ...,Xm } is a set partition of X into m + 1 parts where
∀i ∈ {0,...,n − 1}∀k ∈ {0,...,m} : f(i) = k ⇐⇒ i ∈ X .
                                                k
(23)

In order to describe the inverse of σ, we may assume that in a partition X = {X0,...,Xm } of the set X the inequalities

minX0 ≤ minX1 ≤ ...≤ min Xm
(24)
hold. Then σ1(X) = f such that (23) holds.

Export of Partition

restrictedGrowthArrays: MachineInteger -> Generator PrimitiveArray MachineInteger

Usage

macro I == MachineInteger;
setPartitions(n: I): Generator Array List Integer == generate {
  zero? n => break;
  for a in restrictedGrowthArrays n repeat {
    m := a.0;
    r: Array List Integer := new(next m, empty);
    for i in prev n .. 1 by -1 repeat {
      j := a.i;
      r.j := cons(i, r.j);
    }
    r.0 := cons(0, r.0);
    yield r;
  }
}
for sp in setPartitions 4 repeat stdout << sp << newline;

Parameters

n: MachineInteger

A positive number that gives the length of the restricted growth array.

Description

Generates restricted growth arrays of a given size.

A restricted growth array is not a commonly know in the literature and only used here to efficiently use the array representation of a restricted growth function.

A restricted growth array is identical to a restricted growth function except for the zeroth entry. A restricted growth array of length n > 0 is an array a of non-negative integers such that

a0 = 1 + max{0,a1,...,an−1} (25)
ai 1 + max{0,a1...,ai−1}, if 1 i < n. (26)
The entry a0 of a restricted growth array a gives the number of sets in the partition that corresponds to the restricted growth array.

The call g:=restrictedGrowthArrays(n) returns a generator that generates all restricted growth arrays of size n in lexicographical order starting with [1,0,,0] and finishing [n,1,2,,n 1].

Remarks

For efficiency reasons, the arrays given by the generator might be reused internally, therefore the information should be copied before the generator is stepped again.

153exports: Partition 147a+   (146)  149a
restrictedGrowthArrays: MachineInteger -> Generator PrimitiveArray MachineInteger;

Uses Generator 617 and MachineInteger 67.

Internally it uses an auxiliary array m whose entries are defined in the following way

     {
      0                      if i = 0,
mi =  1 + max {0,a1,...,ai−1}  if 1 ≤ i < n.
(27)
Equation (26) can now be written as
ai mi, if 1 i < n. (28)

The function restrictedGrowthArrays starts with initializing

a = [1,0,,0] m = [0,1,,1].
The conditions (25), (27), and (28), are invariants of the loop below. In the loop, we find the first position i from the right where ai⁄=mi and stop if i = 0. Note that the first index in an array is 0.
155aimplementation: Partition 148b+   (146)  149b  157
restrictedGrowthArrays(n: I): Generator PrimitiveArray I == generate {
        assert(n > 0);
        a: PrimitiveArray I == new(n, 0); a.0 := 1;
        m: PrimitiveArray I == new(n, 1); m.0 := 0;
        local (tw: TextWriter) << (a: PrimitiveArray I): TextWriter == {
                import from String;
                tw := tw << "[" << a.0;
                for j in 1..prev n repeat tw := tw << ", " << a.j;
                tw << "]";
        }
        repeat {
                yield a;
                search for maximal i with ai⁄=mi 155b
                zero? i => break; -- finished
                a.i := ai := next(a.i);
                update arrays a and m 156
        }
}

Uses Generator 617, I 47, and String 65.

Note m0 = 0 is never changed after initialization, so that m0⁄=a0 > 0 ensures the termination of the of the loop at i = 0.

155bsearch for maximal i with ai⁄=mi 155b  (155a)
i := prev n; while a.i = m.i repeat i := prev i;

We have increased to a new “digit” ai and thus must start, behind it with 0 values.

The maximum value that the new digits can take is either mi if ai is still smaller than this value or it is 1 + ai.

156update arrays a and m 156  (155a)
a.0 := mi := if ai = m.i then next ai else m.i;
for j in next i .. prev n repeat {a.j := 0; m.j := mi}
8.9.2 Generating Set Partitions

Generating set partitions is easy via the correspondence (23) if a restricted growth array is known. We only have to take care that our elements of the input list s are of type L. Thus we use the index of the input list as a correspondence to the restricted growth array. Basically (with the notation below), (23) turns into

                     s0 ∈ r0
∀i ∈ {1,...,n − 1} ∀k ∈ {0,...,m } : ai = k ⇐⇒ si ∈ rk.

In the following we want to preserve the order of the elements in the given list s also in the resulting sets of the partition. For that reason, we first reverse the list s. At the same time we determine the length n of the list.

Note that we must treat the empty (input) list in a special way. There exists exactly one partition of the empty set, namely .

157implementation: Partition 148b+   (146)  155a  158
structures(s: SetSpecies L): Generator % == {
        empty? s => generate yield per([]$Rep); -- empty partition
        (s0, s) := (first s, rest s);
        u: List L := empty;
        n: I := 1;
        while not empty? s repeat {
                (u, s) := (cons(first s, u), rest s);
                n := next n;
        } -- u = reverse(s :: List L), s0 is missing.
        generate {
                import from PrimitiveArray MachineInteger;
                for a in restrictedGrowthArrays n repeat {
                        m := a.0;
                        r: Array List L := new(m, empty);
--                        assert(prev n = #u);
--                        for i in prev n .. 1 by -1 for l in u repeat {
                        i := n; v := u;
                        while not empty? v repeat {
                                i := prev i;
                                (l, v) := (first v, rest v);
                                k := a.i;
                                r.k := cons(l, r.k);
                        }
                        r.0 := cons(s0, r.0);
                        yield per r;
                }
        }
}

Uses Array 599, Generator 617, I 47, MachineInteger 67, and SetSpecies 117.

8.9.3 Generating Integer Partitions

An isomorphism type of a set partition of a set of cardinality n is, basically, the same as an integer partition of n. The (multi-)set of cardinalities of the sets in the set partition is an integer partition.

The implementation is, in fact, very similar to the implementation of integerPartitions, but here we carry the labels along so that each label is used exactly once.

158implementation: Partition 148b+   (146)  157  160
isomorphismTypes(s: SetSpecies L): Generator % == {
        n: I := #s;
        isomorphismTypes(s :: List L, n, n, 0);
}

Uses Generator 617, I 47, and SetSpecies 117.

The following functions returns all isomorphism types of partitions of n into parts of size that is not bigger than bound. The last argument len is a counter the increases with every recursive call of the function. It encodes the number of parts of the partition.

159implementation: Partition: auxiliary functions 159  (146)
local isomorphismTypes( -- integer partitions
    s: List L,
    n: I,
    bound: I,
    len: I -- length of the partition, this is a counter
): Generator % == generate {
        assert(#s=n);
        zero? n => yield per(new(len)$Rep);
        minNBound := min(n, bound);
        u: List L := empty;
        v: List L := s;
        for i in 1..minNBound repeat (u, v) := (cons(first v, u), rest v);
        m := minNBound;
        while m > 0 repeat {
                assert(#u=m);
                reverseU := reverse u;
                for p in isomorphismTypes(v, n-m, min(m,bound), len+1) repeat {
                        rep(p).len := reverseU;
                        yield p;
                }
                (u, v) := (rest u, cons(first u, v));
                m := prev m;
        }
}

Uses Generator 617 and I 47.

8.9.4 The Number of Set Partitions

See [KS98, Chp. 3.2].

The number of set partitions is given by the Bell number defined as

       B(0) = 1
       n−1(     )
B (n) = ∑   n − 1 B (i).
       i=0    i
(29)

(30)

Since we encode the Bell numbers in an exponential generating series, we have to multiply by i! in the code below and finally divide by n!.

160implementation: Partition 148b+   (146)  158  162
generatingSeries: ExponentialGeneratingSeries == {
        macro R == Fraction Integer;
        bell(n: I, s: DataStream R): R == {
                import from Integer, DataStream Integer;
                zero? n => 1;
                m: I := prev n;
                r: R := 1;
                for i: I in 1..m repeat {
                        b := binomial(m, i)$MultinomialTools;
                        b := b * factorialStream i;
                        r := r + b * s.i;
                }
                inv(factorialStream n) * r
        }
        (stream(bell) $ DataStream(R)) :: ExponentialGeneratingSeries;
}

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

8.9.5 The Number of Integer Partitions

To calculate the number of integer partitions of n, we use the O(√n--) recurrence from [AS72, p. 825]:

         ∑
p(n) =         (− 1)k−1p(n − i).
        1≤i,k≤n
       i=12(3k2±k)
(31)
We obviously have
1
2(3k2 + k) = 1
2(3k2 k) + k, (32)
1
2(3(k + 1)2 (k + 1)) = 1
2(3k2 + k) + 2k + 1. (33)
so we can increment k and i in the following loop by means of those two equalities. We take care of the sign by just repeating the code with a minus sign instead of a plus sign. Of course, we have to stop summation as soon as the index i is bigger than n.
162implementation: Partition 148b+   (146)  160  163a
partition(n: I, p: DataStream Z): Z == {
        zero? n => 1;
        (r, i, k) := (0$Z, 1$I, 1$I);
        repeat {
                (r, i)    := (r+p(n-i), i+k);            i>n => break;
                (r, i, k) := (r+p(n-i), i+k+k+1, k+1);   i>n => break;
                (r, i)    := (r-p(n-i), i+k);            i>n => break;
                (r, i, k) := (r-p(n-i), i+k+k+1, k+1);   i>n => break;
        }
        r;
}
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == {
        (stream(partition)$DataStream(Z))::OrdinaryGeneratingSeries;
}

Uses DataStream 386, I 47, OrdinaryGeneratingSeries 311, and Z 47.

According to [BLL98, Chp. 1.4] we have

                        (    (       )    )
                   ∑  1       ∑   xkn
ZPar(x1,x2,...) = exp   n-(exp (    -k-) − 1)
                   n≥1        k≥1
(34)

It is necessary to explicitly define a local function divideBy, since otherwise, all series are multiplied with the same factor. For a demonstration of the bug see BUG 5.

163aimplementation: Partition 148b+   (146)  162  163b
local cis(): CycleIndexSeries == BugWorkaround(
    CycleIndexSeries has with {exponentiate: % -> %}
){
        import from I, Z, P;
        ciset := (cycleIndexSeries $ SetSpecies(Z)) :: DataStream(P);
        summand(n: I): CycleIndexSeries == {
                invN: Q := inv(n::Z);
                cisSetDividedByN: Generator P := generate {
                        yield 0$P;
                        for p in elements(ciset, 1) repeat yield invN*p;
                }
                stretch(cisSetDividedByN :: CycleIndexSeries, n);
        }
        exponentiate sum(summand n for n:I in 1..);
}
cycleIndexSeries: CycleIndexSeries == cis();

Uses BugWorkaround 48, CycleIndexSeries 330, DataStream 386, Generator 617, I 47, Q 47, SetSpecies 117, and Z 47.
163bimplementation: Partition 148b+   (146)  163a  163c
(tw: TextWriter) << (x: %): TextWriter == tw << rep x;
163cimplementation: Partition 148b+   (146)  163b  164
(x: %) = (y: %): Boolean == rep x = rep y;
164implementation: Partition 148b+   (146)  163c
import from String;
expression: SpeciesExpression == leaf("Partition");

Uses Partition 146, SpeciesExpression 430, and String 65.