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

Printing Boolean Input Combinations in Scala

Someone at school recently asked me to help him write some code in Scala to print out the [latex]2^n[/latex] Boolean input combinations that are possible with [latex]n[/latex] variables. I decided to start off with [latex]n=4[/latex] variables to keep things simple and verifiable. After a couple of minutes of hacking around, I came up with the following code:The cool part is the shifting modulus check. I'm actually kind of proud of it. It enabled me to write the code using only two loops! Here is the result: -a -b -c -d +a -b -c -d -a +b -c -d +a +b -c -d -a -b +c -d +a -b +c -d -a +b +c -d +a +b +c -d -a -b -c +d +a -b -c +d -a +b -c +d +a +b -c +d -a -b +c +d +a -b +c +d -a +b +c +d +a +b +c +d Also, please note that this is probably, by no means, the most functional way to do this. It was merely an attempt at hacking together some code that just gets the job done. If I have time, I will write up some posts on functional ways to produce both combinations and permutations in Scala.

Quick Thoughts on STM (Software Transactional Memory) in Scala (Akka, et al)

Judging from the fact that Odersky's new company, Typesafe, is including Akka in their Typesafe Stack means that there must be a growing interest in concurrency, actors, and Software Transactional Memory (STM) among Scala developers. Personally, (and I regret to say it) the only area in which I'm really familiar with Transactional Memory is with regards to database systems. Anyway, after reading up on STM, I think I'm going to try and apply it my next couple of Scala projects.

Does anyone have any novel ideas in this area? Any papers I need to read? Etc?

Implicit additions to types for DSL's (Scala)

One of the goals when designing an embedded/internal domain-specific-language (DSL) is extend the syntax of the host language in order to make operations and syntax more clear within a particular domain. However, most host languages don't provide a way for you to extend the operations or methods available to built-in types. This often leads to the creation of new types that provide both the same functionality as the built-in type and the extended functionality needed within a domain-specific context. In Scala, adding functionality to built-in types is easy. It can be achieved by harnessing the power of Scala's implicit conversions. This is made possible because of a couple of reasons. First, everything in Scala is an object. Second, there is no real difference between operations and methods. Third, when an operation or method doesn't exist for a given object's type, Scala checks to see if that object can be implicitly converted to a type that does provide that method.

Here's an example of how to add an "elemOf" operator to all types in Scala. Such an operator, by definition, would tester whether an element is an element of a Set. In order to do this, we need to create a wrapper class that defines the "elemOf" operator.

Note, we haven't done anything special. If we were to stop here, we'd have to explicitly create an instance of DSLRichAny anytime we wanted to use the "elemOf" operator. The magic happens when we tell Scala to implicitly create a new instance of DSLRichAny. Let's do this by creating an object for our DSL in which we define such an implicit conversion.

Now, any object that extends our DSL object will know that there is way to implicitly convert any object to an instance of DSLRichAny! Here's an example.

When the application is compiled, Scala sees that the "elemOf" operator/method is being called on a type that doesn't define it. It therefore checks to see if there is an implicit conversion defined, in scope, that would allow "elemOf" to be called. Since we're extending our DSL object, such a conversion is in scope and the compiler does the rest.