#### 11.3 Multinomial Coefficients

Definition 11.2. Let k1,,kr be non-negative integers and n = i=1rki. The multinomial coefficient is defined by equation 164. It is undefined for n i=1rki.

Export of MultinomialTools

multinomial: List MachineInteger -> Integer

Usage

k: List I := [k1, ..., kr];
b: Integer := multinomial k;

Parameters

ki: MachineInteger

For each i the parameter ki is a (machine-size) integer.

Description

Compute multinomial coefficient.

For non-negative integers k1,,kr the function multinomial computes the multinomial coefficient

 (164)
If x < 0 for some x k then multinomial(k)=0.

Remarks

We explicitly define multinomial([]) as 1.

379exports: MultinomialTools 369+   (367)  369  381
multinomial: List MachineInteger -> Integer;

Uses Integer 66 and MachineInteger 67.
380implementation: MultinomialTools 370a+   (367)  373  382
multinomial(k: List I): Integer == {
empty? k => 1;
n: I := 0;
for i in k repeat {
if i < 0 then return 0;
n := n + i;
}
multinomial(n, k);
}

Uses I 47 and Integer 66.

Export of MultinomialTools

multinomial: (I, List I) -> Integer

Usage

macro I == MachineInteger;
k: List I := [k1, ..., kr];
n: I := 0;
for i in k repeat n := n + i;
b := multinomial(n, k);

Parameters

n: I

This must be i=1rki.

ki: I

For each i the parameter ki is a non-negative integer.

Description

Compute multinomial coefficient.

For non-negative integers k1,,kr with r > 0 the function multinomial computes the multinomial coefficient

 (165)

Remarks

Note that the output of the function is undefined for n i=1rki. It is also undefined, if the input list is empty.

381exports: MultinomialTools 369+   (367)  379
multinomial: (I, List I) -> Integer;

Uses I 47 and Integer 66.

Our implementation uses the following connection to binomial coefficients:

 = (166) = ⋅ (167) = ⋅ (168)
and thus just compute r 1 products of integers.
382implementation: MultinomialTools 370a+   (367)  380
multinomial(n: I, k: List I): Integer == {
assert(not empty? k);
assert({local s: I := 0; for i in k repeat s:=s+i; s=n});
empty? k => 1;
m: I := first k;
k := rest k;
empty? k => 1; -- binom(m, m) = 1
binomial(n, m)\$% * multinomial(n-m, k);
}

Uses I 47 and Integer 66.
383UNUSED ITERATIVE VERSION: implementation: MultinomialTools 383
multinomial(n: I, k: List I): Integer == {
r: Integer := 1;
while not empty? k repeat {
m: I := first k;
r := r * binomial(n, m)\$%;
n := n - m;
k := rest k;
}
r;
}

Uses I 47 and Integer 66.