 # Multinomial Coefficients in Scala using Fold

Multinomial coefficients are often denoted as $$\left( n;~ k_1, \dots, k_m \right)$$ where $$n = \sum_{i=1}^m k_i$$. Another way to express a multinomial coefficient is using the $${\rm choose}$$ notation commonly employed in combinatorics for binomial coefficients. Given $$n \geq \sum_{i=1}^{m-1} k_i$$, we say that the following are equivalent:

$$\left( n;~ k_1, \dots, k_m \right) ~\mbox{where}~ k_m = n - \sum_{i=1}^{m-1} k_i \equiv {n \choose k_1, \dots, k_{m-1}}$$

For convenience, I'm going to use the first notation.

### Theorem

I'm not sure if this has ever been stated before, but here's an observation that I made a couple months ago:

$$\left( n;~ k_1, \dots, k_m \right) = \left( n-k_m;~ k_1, \dots, k_{m-1} \right) \cdot \frac{1}{k_m !} \prod_{i=1}^{k_m} n-i+1$$

That is, there exists a linear, tail recursive definition for calculating multinomial coefficients.

### Proof of Theorem

Without loss of generality, assume that $$n = \sum_{i=1}^{m} k_i$$. According to the equivalence noted above as well as the Multinomial Theorem, we have:

$$\left( n;~ k_1, \dots, k_m \right) = {n \choose k_1, \dots, k_m} = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_m ! }$$

(1) If we pull out the term $$k_m$$, we get:

$$\left( n;~ k_1, \dots, k_m \right) = \frac{1}{k_m !} \cdot \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! }$$

(2) Now, let's find some $$\zeta$$ such that:

$$\frac{ (n-k_m)! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \zeta = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! }$$

(3) If we isolate $$\zeta$$ on the left-hand side, we observe the following:

$$\zeta = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \frac{ k_1 ! \cdot \cdots \cdot k_{m-1} ! }{ (n-k_m)! } = \frac{ n! }{ (n-k_m)! }$$

(4) We know that certain terms cancel in this fraction. It is easy to see that

$$\zeta = \frac{ n! }{ (n-k_m)! } = (n - k_m + 1) \cdot (n - k_m + 2) \cdot \cdots \cdot n = \prod_{i=1}^{k_m} n - k_m + i$$

(5) Since the product in $$\zeta$$ is from $$1$$ to $$k_m$$, we can be further simplify the expression to

$$\zeta = \prod_{i=1}^{k_m} n - k_m + i = \prod_{i=1}^{k_m} n-i+1$$

(6) Replacing $$\zeta$$ in (2) gives us the following:

$$\frac{ (n-k_m)! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \prod_{i=1}^{k_m} n-i+1 = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! }$$

(7) Now we use the result of (6) with (1) to get:

$$\left( n;~ k_1, \dots, k_m \right) = \frac{1}{k_m !} \cdot \frac{ (n-k_m)! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \prod_{i=1}^{k_m} n-i+1$$

(8) Since the second fraction in (7) can be expressed as a multinomial, we have:

$$\left( n;~ k_1, \dots, k_m \right) = \left( n-k_m;~ k_1, \dots, k_{m-1} \right) \cdot \frac{1}{k_m !} \prod_{i=1}^{k_m} n-i+1$$

Therefore, the theorem is correct.

### Some Notes

This result that we observed in (7) directly relates to the ratios between the coefficients on the face of a multidimensional Pascal triangle.

### Corollary

It is easy to see that the following follows from the theorem:

$$\left( n;~ k_1, \dots, k_m \right) = \left( n-k_m;~ k_1, \dots, k_{m-1} \right) \cdot \prod_{i=1}^{k_m} \frac{n-i+1}{i}$$

### Folding with scala

In Scala, the expression in the corollary can be expressed concisely using the foldLeft operator.This operator applies a binary operator to a start value and all elements of a list, going left to right. If we let our list be the numbers $$1, \dots, k_m$$, then we can foldLeft with the following binary operator:

$$\left(a,b\right) \Rightarrow \frac{a \left(k_m-b+1\right)}{b}$$

For more information on the general fold operator (with which you can pretty much do anything with), see "Introduction to Metamathematics" by Kleene (affiliate link).

### The Code

Here is my recursive implementation of the recurrence relation mentioned in the corollary above:

I've omitted a an iterative implementation of the corollary that I've written for the sake of brevity. If anyone expresses some interest, I may include here or in a future blog post.

object Combinatorics {     /** Computes the multinomial coefficient (n; k_1, .., k_m)      *  where n = the sum of k_1, .., k_m.     *      *  This is a variadic convenience function that allows      *  someone to invoke <code>multi</code> without using an      *  array. Note, however, that the variadic parameter is      *  transformed into an array when this version of      *  <code>multi</code> is invoked.     *      *  @author Michael E. Cotterell <mepcotterell@gmail.com>     *  @param  k items to choose     */    def multi (k: Int*): Long = multi(k.toArray)     /** Computes the multinomial coefficient (n; k_1, .., k_m)      *  where n = the sum of k_1, .., k_m.      *      *  This implementation requires exactly n-many      *  multiplications and m-many recursive calls.     *       *  @see    http://michaelcotterell.com/2013/03/multinomial-coefficients/      *  @author Michael E. Cotterell <mepcotterell@gmail.com>     *  @param  k items to choose     */    def multi (k: Array[Int]): Long =     {        if (k.length == 1) 1L        else {            (1 to k.last).foldLeft(multi(k.slice(0, k.length - 1))){                (prev, i) => prev * (k.sum - i + 1) / i            }        } // if    } // multi     /** Computes the multinomial coefficient (n; k_1, .., k_m)      *  where n = the sum of k_1, .., k_m.     *      *  This implementation requires exactly n-many      *  multiplications and m-many recursive calls. Also, it is      *  experimentally slower than the <code>foldLeft</code>      *  implementation provided by the <code>multi</code>      *  function.     *       *  @see    http://michaelcotterell.com/2013/03/multinomial-coefficients/     *  @author Michael E. Cotterell <mepcotterell@gmail.com>     *  @param  k items to choose     */    def _multi (k: Array[Int]): Long =     {        if (k.length == 1) 1L        else {            var product = _multi(k.slice(0, k.length-1))            for(i <- 1 to k.last) product = product * (k.sum-i+1) / i                        product        } // if    } // _multi } // Combinatorics