The multinomial theorem is a statement about expanding a polynomial when it is raised to an arbitrary power. Rather than just stating the theorem and showing examples, we motivate the theorem by a concrete example of finite random sampling. This example demonstrates that the notion of finite sampling provides another interpretation to the multinomial thoerem. As a result, the multinomial theorem and the multinomial coefficients are useful in combinatorial techniques in finite random sampling models. The multinomial coefficients are also useful in partitioning a set of objects into several subgroups where each subgroup is made up of indistinguishable objects. See the post The game of poker dice and the multinomial theorem for an example of applications of these ideas.
Suppose we have a finite set with elements where is a positive integer. Suppose we select elements from the population with replacement. We consider ordered samples of size and unordered samples of size . To make this notion more concrete, consider the population consisting of letters . Suppose we sample times with replacement. The following are two specific ordered samples of size :
Thus ordered samples can be represented as strings of characters drawn from the population presented in the order in which the objects are drawn. In this example, there are many ordered samples. Each character drawn has choices and the drawing is done times. In general, if the population has size , then there are many ordered samples of size .
We now look at unordered samples obtained from sampling times from the population . In unordered samples, the order in which the letters are drawn is no longer important (or recorded). We only care about the number of instances each letter is selected. Thus each of the ordered samples shown above yields the same unordered sample: , , and . We represent the unordered sample in two ways:
The first representation is a -tuple where the coordinates are the number of , the number of , the number of and the number of in the selections. Thus, the sum of the coordinates must be (the total number of selections). The second representation of the unordered sample is made up of stars and bars. The three bars create spaces and the stars in each space represent the number of characters drawn. We would like to point out that the “unordered” in the unordered samples refers to the fact that the order in which the objects are drawn is immaterial. However, both the -tuple notation and the stars and bars diagrams are ordered according to the letters in the population (showing how many instances each object appears in the samples).
The star and bar diagram has a combinatorial advantage. For example, how many unordered samples are there when you draw letters with replacement from the population ? In any unordered sample, there are bars and stars. The order of the stars and bars can be in any arbitrary order. Thus there are many unordered samples. In general, if the population size is , then there are many unordered samples, either represented as -tuples or stars and bars diagrams with bars and stars.
One more note about the number calculated above. This is also the total number of non-negative integer solutions to the equation . Thinking of an unordered sample as a -tuple, the sum of the coordinates must be . This observation is important to understanding the multinomial theorem.
There is one more count associated with unordered samples. How many unordered samples are there when you draw letters with replacement from the population such that each letter is selected at least once? The answer is . Suppose that each letter is already selected once. Then we need to sample more times out of these letters. According to the above paragraph, the total count is . To generalize, if the population size is , there are many unordered samples in which all objects in the population are represented in each sample.
We now tie unordered samples back to ordered samples. How many ordered samples are equivalent to the unordered sample ? Both ordered samples in are equivalent to (i.e. each letter is drawn the same number of times). In other words, how many -character strings can be formed using , , and ? The answer is:
The reasoning for the above calculation is that out of positions in the strings, we choose position for the , choose positions for the in the remaining positions and so on.
Summary of the example
In sampling times with replacement from the population , we summarize our observations about the example.
- The number of ordered samples is .
- The number of unordered samples is . Furthermore, the number of non-negative integer solutions to the equation is .
- The number of unordered samples where each letter is selected is . Furthermore, the number of positive integer solutions to the equation is .
- For any unordered sample where , the total number of ordered samples equivalent to this unordered sample is . As we shall see, these are called multinomial coefficients.
Note the interplay between the ordered samples and unordered samples. We start out with a large number of ordered samples ( many). We then collapse these ordered samples to just unordered samples. We see that each unordered sample corresponds to certain number of ordered samples according to the multinomial coefficients. Thus we have the following sum where are non-negative integers:
The Multinomial Theorem
With the preceding discussion, we now state the multinomial theorem.
The Multinomial Theorem
For any positive integer and any positive integer , we have the following polynomial expansion:
The same observations we make about the example apply. For example, the number of terms in the polynomial expansion is , which is the number of non-negative integer solutions to the equation . Each term in the polynomial expansion can be considered as an unordered sample in the finite sampling with replacement. Then the coefficient of each term (called multinomial coefficient) is the number of associated ordered samples. As a result, the multinomial coefficients sum to .
We conclude with two interpretations of the multinomial coefficient.
If we have many distinct symbols (say ) and we have many , many and so on, then the multinomial coefficient in is the number of -length character strings that can be formed using the available symbols.
Another interpretation is that of partitioning a set of objects into subgroups where the objects in each subgroup are indistinguishable.
Both interpretations are one and the same, just looking at the same result in a different angle. For example, all three of the following yield the same answer: . We have letters (one , four , four and two ), how many character strings can be formed with these letters?
On the other hand, we have identical candies randomly distributed to Marcus, Issac, Samantha and Paul. How many ordered samples will result if Marcus receives one candy, Issac receives four candies, Samantha receives four candies and Paul receives two candies? Here, we are trying to partition a set of objects into four subgroups where one group has one element, two of the groups have four elements each and another group has two elements.
If we have candidates for forming four distinct committees where one committee has one member, two of the committees have four members each and another one has two members. In how many ways can this be done?
- Feller, W., An Introduction to Probability Theory and its Applications, Vol. I, 3rd ed., John Wiley & Sons, Inc., New York, 1968
Revised March 28, 2015