Multinomial Coefficients

[Home] [prev] [up] [next] ((src/multinom.as))

11.3 Multinomial Coefficients

Definition 11.2. Let k₁,…,k_r be non-negative integers and n = ∑ _i=1^rk_i. The multinomial coefficient ( n )
k1,k2,...,kr is defined by equation 164. It is undefined for n∑ _i=1^rk_i.

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 k_i is a (machine-size) integer.

Description

Compute multinomial coefficient.

For non-negative integers k₁,…,k_r the function multinomial computes the multinomial coefficient

( k1 +⋅⋅⋅+ kr ) (k1 + ⋅⋅⋅+ kr)!
k , k , ..., k = --k-!⋅⋅⋅k!---.
1 2 r 1 r

(164)

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

Remarks

We explicitly define multinomial([]) as 1.

379⟨exports: MultinomialTools 369⟩+≡ (367) ⊲369 381 ⊳
multinomial: List MachineInteger -> Integer;

Uses Integer 66 and MachineInteger 67.

380⟨implementation: 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=1^rk_i.
ki: I: For each i the parameter k_i is a non-negative integer.

Description

Compute multinomial coefficient.

For non-negative integers k₁,…,k_r with r > 0 the function multinomial computes the multinomial coefficient

( r ) n!
k , k , ..., k = k-!⋅⋅⋅k!.
1 2 r 1 r

(165)

Remarks

Note that the output of the function is undefined for n∑ _i=1^rk_i. It is also undefined, if the input list is empty.

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

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

383⟨UNUSED 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.

[Home] [prev] [up] [next] ((src/multinom.as))