Multinomial coefficients are sometimes denoted as \( \left( n;~ k_1, \dots, k_m \right) \) where \( n = \sum_{i=1}^m k_i \). Another, perhaps more familiar, 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:
$$ {n \choose k_1, \dots, k_{m-1}} \equiv \left( n;~ k_1, \dots, k_m \right) ~\mbox{where}~ k_m = n – \sum_{i=1}^{m-1} k_i $$
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 $$
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.
