The multinomial coefficients

Consider the following four examples of counting:

Consider the finite populaton $\left\{m,i,s,p\right\}$ . Draw 11 letters at random from this population with replacement. The total number of 11-character letter strings that can be formed is $4^{11}$ . How many of these character strings contain one m, four i’s, four s’s and two p’s?
What is the total number of 11-character strings that can be formed using the letters in the word Mississippi?
Suppose each of the questions in an 11-question multiple choice test has 4 choices (M, I, S and P). A student chooses the answers by pure guessing. How many ways can this student take the test if the random selection of the answers produces 1 M, 4 I’s, 4 S’s and 2 P’s as answers?
How many ways can we randomly assign 11 candidates into 4 committees such that Committee M consists of 1 member, Committee I consists of 4 members, Committee S consists of 4 members and Committee P consists of 2 members? Assume that each candidate can only be assigned to one committee.

All four examples have the same answer, namely 34,650. All these examples are about the number of ways of assigning 11 objects into four subgroups, one containing 1 object, two containing 4 objects each and one containing 2 objects, where the objects in each subgroup are considered indistinguishable. These four examples illustrate the combinatorial approach called multinomial coefficients. The multinomial coefficient (the number of ways of assigning the 11 objects in the specified manner) in these examples is:

$\displaystyle \frac{11!}{1! \ 4! \ 4! \ 2!}=34650$

In this post, I make a few observations about the combinatorics surrounding the multinomial coefficients and the multinomial theorem. The multinomial distribution is then naturally defined.

First, the multinomial coefficients. Suppose $k$ and $n$ are positive integers such that $n \le k$ . Suppose we have nonnegative integers $a_1, a_2, \cdots, a_n$ such that $a_1+a_2+\cdots+a_n=k$ . The following is the number of ways to partition a set of $k$ distinct objects into $n$ subgroups where the first subgroup consists of $a_1$ objects, the second subgroup consists of $a_2$ objects and so on.

$\displaystyle (0) \ \ \ \ \binom{k}{a_1, a_2, \cdots, a_n}=\frac{k!}{a_1! a_2! \cdots a_n!}$

The result $(1)$ is the result of a combinatoric observation below. The result $(2)$ is the multinomial theorem.

$\displaystyle (1) \ \ \ \ \sum_{a_1+a_2+ \cdots + a_n=k} \frac{k!}{a_1! a_2! \cdots a_n!}=n^k$

$\displaystyle (2) \ \ \ \ (x_1+x_2+ \cdots +x_n)^k=\sum_{a_1+a_2+ \cdots + a_n=k} \frac{k!}{a_1! a_2! \cdots a_n!} \ x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$

Discussion of Example
In drawing 11 letters at random with replacement from the set $\left\{m,i,s,p\right\}$ , there are a total of $4^{11}=4194304$ many ordered samples. The following two strings are two examples:

$Mississippi \ \ \ \ \ \ \ \ \ \ \ Mississiipp$

Both of these ordered samples have one m, four i’s, four s’s and two p’s. In other words, both of these ordered samples have the same unordered sample $\left\{m,i,i,i,i,s,s,s,s,p,p\right\}$ . A more compact way of notating this unordered sample is $(1,4,4,2)$ , where the first coordinate is the number of m’s, the second coordinate is the number of i’s, the third coordinate is the number of s’s, and the fourth coordinate is the number of p’s. Note that the sum of the four is 11. The number of ordered samples that are tied to $(1,4,4,2)$ is the multinomial coefficient 34650 as indicated above.

Another way of denoting the unordered sample $(1,4,4,2)$ is using a string of stars and bars as follows:

$* \ | \ * \ * \ * \ * \ | \ * \ * \ * \ * \ | \ * \ *$

In the star and bar diagram, there are 11 stars (representing the 11 characters selected) and 3 bars (creating four spaces representing the letters m, i, s and p, respectively). The star and bar diagram has a combinatorial advantage. For example, how many unordered samples are there when 11 letters are selected at random with replacement from $\left\{m,i,s,p\right\}$ ?

In any unordered sample in our discussion, there are 3 bars and 11 stars. The stars and bars can be in any arbitary order. Thus there are $\displaystyle \binom{11+3}{11}=364$ many unordered samples. Furthermore, the equation $a_1+a_2+a_3+a_4=11$ has 364 many nonnegative integer solutions.

A related question is: how many unordered samples are there when 11 letters are selected at random with replacement from $\left\{m,i,s,p\right\}$ such that each letter is selected at least once? In the star and bar diagram, each of the four spaces has at least one star. Thus we need to arrange 7 more stars in these four spaces. Thus there are $\displaystyle \binom{7+3}{7}=120$ many ways of doing this. Furthermore, the equation $a_1+a_2+a_3+a_4=11$ has 120 many positive integer solutions.

Generalization
Suppose we sample $k$ times from the finite set $\left\{x_1,x_2,x_3, \cdots, x_n\right\}$ with replacement. There are $n^k$ many ordered samples. These ordered samples can be collapsed into

$\displaystyle (3) \ \ \ \ \binom{k+n-1}{k}=\binom{k+n-1}{n-1}$

many unordered samples (this can be seen using the star and bar diagram). Furthermore, the number of nonnegative integer solutions to the equation $a_1+a_2+ \cdots +a_n=k$ is obtained by $(3)$ .

The number of ordered samples tied to the unordered sample $(a_1,a_2, \cdots, a_n)$ is:

$\displaystyle (4) \ \ \ \ \frac{k!}{a_1! a_2! \cdots a_n!} \ \ \ \ \text{(multinomial coeffcients)}$

The preceding discussion is encapsulated in equation $(1)$ . The equation $(2)$ above is the statement of the multinomial theorem, which is a statement about polynomial expansion. The number of terms in the polynomial expansion is indicated by $(3)$ , which is also the number of nonnegative integer solutions to the equation $a_1+a_2+ \cdots +a_n=k$ . Each term $x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$ in the polynomial expansion can be considered as an unordered sample in the finite sampling with replacement. Thus both results of $(1)$ and $(2)$ are compact ways of describing the finite sampling with replacement from the set $\left\{x_1,x_2,x_3, \cdots, x_n\right\}$ .

The number of unordered samples where each object in $\left\{x_1,x_2,x_3, \cdots, x_n\right\}$ is selected at least once is:

$\displaystyle (5) \ \ \ \ \binom{k-n+n-1}{k-n}=\binom{k-n+n-1}{n-1}=\binom{k-1}{n-1}$

As a result, $(5)$ provides the number of positive integer solutions to the equation $a_1+a_2+ \cdots +a_n=k$ .

The Multinomial Distribution
Suppose that $k$ independent trials are performed where each trial has $n$ outcomes denoted by $E_1,E_2,\cdots,E_n$ . Suppose that in each trial, the probability of the outcome $E_i$ is $\displaystyle p_i$ . Furthermore, we have $p_1+p_2+\cdots+p_n=1$ .

The result of performing the $k$ independent trials can be denoted by an ordered string such as $E_5 E_1 E_7 \cdots$ , i.e. an ordered sample when sampling $k$ times from $\left\{E_1,E_2,\cdots,E_n\right\}$ with replacement. Consider the ordered samples where the outcome $E_1$ occurs $a_1$ times, the outcome $E_2$ occurs $a_2$ times and so on such that $a_1+a_2+\cdots+a_n=k$ . This is a scenario that is equivalent to the four examples indicated at the beginning of the post, which is about assigning $k$ trials into $n$ subgroups, the first of which consists of $a_1$ occurrences of the outcome $E_1$ , the second subgroup consists of $a_2$ occurrences of the outcome $E_2$ and so on. The multinomial coefficient $(4)$ above is the number of all such ordered samples. Thus the following is the probability that in $k$ trials, $E_1$ occurs $a_1$ times, $E_2$ occurs $a_2$ times (and so on):

$\displaystyle \frac{k!}{a_1! \ a_2! \cdots a_n!} \ p_1^{a_1} \ p_2^{a_2} \cdots p_n^{a_n}$

More formally, for each $j=1,2, \cdots, n$ , let $X_j$ be the number of times the event $E_j$ occurs in the $k$ many trials. Then the joint distribution of the random variables $X_1,X_2,\cdots,X_n$ is called the multinomial distribution with parameters $k,p_1,p_2,\cdots,p_n$ .

The joint probability density function (joint pdf) is given by:

$\displaystyle P(X_1=a_1,X_2=a_2, \cdots, X_n=a_n)=\frac{k!}{a_1! \ a_2! \cdots a_n!} \ p_1^{a_1} \ p_2^{a_2} \cdots p_n^{a_n}$

The multinomial distribution is so named is because of the multinomial theorem. Note that the right-hand side of the above pdf is a term in the multinomial expansion of $(p_1+p_2+\cdots+p_n)^k$ . Furthermore we have:

$\displaystyle 1=(p_1+p_2+ \cdots +p_n)^k=\sum_{a_1+a_2+ \cdots + a_n=k} \frac{k!}{a_1! a_2! \cdots a_n!} \ p_1^{a_1} p_2^{a_2} \cdots p_n^{a_n}$

When there are only two categories of balls, labeled 1 (success) or 2 (failure), $X_2=k-X_1$ . As a result, $X=X_1$ has a univariate distribution, which is the binomial distribution.

Reference

Feller, W., An Introduction to Probability Theory and its Applications, Vol. I, 3rd ed., John Wiley & Sons, Inc., New York, 1968

2 thoughts on “The multinomial coefficients”

rishabh raman on June 22, 2011 at 8:31 pm said:

Amazing work……I was trying to grasp multinomial theorem and i stumbled on this blog.Excellent !!

Reply ↓
De on October 9, 2016 at 10:04 am said:

Thanks for the blog post – this was really helpful when I was trying to sort out multinomial thm!

Reply ↓

A Blog on Probability and Statistics

The multinomial coefficients

2 thoughts on “The multinomial coefficients”

Leave a Reply Cancel reply

Share this:

Like this:

Related

2 thoughts on “The multinomial coefficients”

Leave a Reply Cancel reply