Multinomial coefficients

This is the fourth post in a series of posts on combinatorial analysis. The post is opened with the following problem. This post builds on the previous post on binomial coefficients.

    Figure 1 – three choices for lunch

Multinomial Lunch Problem
Each of the twelve people have 3 choices for lunch – McDonald, Burger King and IN-N-OUT, all fast food restaurants. The choice for each person is independent of the choices of the other diners.

  1. In how many ways can the lunch choices for this 12-person group be made?
  2. In how many ways can the lunch choices for this 12-person group be made in such a way that 3 people choose McDonald, 4 people choose Burger King and 5 people choose IN-N-OUT?
  3. In how many ways can the lunch choices for this 12-person group be made in such a way that 3 people choose one restaurant, 4 people choose another restaurant and 5 people choose the remaining restaurant?

The previous posts on combinatorial analysis are: binomial coefficients, combination and permutation and multiplication principle.

___________________________________________________________________________

Multinomial Coefficients

The problem for lunch choices is a multinomial coefficient problem. The second question in the problem is equivalent to any one of the following question.

  1. How many ways can a set of 12 distinct objects be divided into 3 subgroups, one consisting of 3 objects, one consisting of 4 objects and one consisting of 5 objects?
  2. How many different 12-letter strings are there consisting of 3 M’s, 4 B’s and 5 I’s?
  3. Suppose each of the questions in a 12-question multiple choice test has three choices (M, D and I). A student chooses the answers by pure guessing. How many of the possible test answers consist of 3 M’s, 4 B’s and 5 I’s?
  4. How many ways can 12 people be assigned to 3 committees such that one committee consists of 3 people, one committee consists of 4 people and one committee consists of 5 people? Assume that each person is assigned to only one committee.
  5. An urn contains three letters M, B and I. Randomly sample 12 letters from the urn with replacement. What is the number of sample results that consist of 3 M’s, 4 B’s and 5 I’s?

The first question is basically the definition of multinomial coefficient. It is the total number of ways to divide a set of objects into several subsets such that each subset is of a pre-determined size. In the second question, the objects are the 12 positions in the letter strings. In the third question, the objects to be divided are the 12 multiple choice questions. In the fourth question, the objects to be divided are the 12 people to be assigned into committees.

The fifth question is from a random sampling perspective. In any of the question, the dividing can be thought of as a choice (or decision) for each object. For each of the 12 objects, should the object be put into group 1, group 2 or group 3 (or should choice 1 be taken, choice 2 be taken, choice 3 be taken)? In the lunch problem, each diner has 3 choices. The choices in their totality would be viewed as the results from a random sampling of the population of 3.

The answer to any of the above questions is a multinomial coefficient.

Multinomial Coefficient

If n_1+n_2+\cdots+n_k=n, the notation for the multinomial coefficient is \displaystyle \binom{n}{n_1,n_2,\cdots,n_k} and is defined by \displaystyle \binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{n_1! n_2! \cdots n_k!}. The multinomial coefficient is the number of ways a set of n distinct objects can be divided into k subsets, one of which consists of n_1 objects, one of which consists of n_2 objects, …., one of which consists of n_k objects.

It is clear that multinomial coefficients are a generalization of binomial coefficients. Instead of having to choose from one of two choices in each random selection, there are multiple choices to choose from. Even the notation \displaystyle \binom{n}{n_1,n_2,\cdots,n_k} is a generalization of the notation \displaystyle \binom{n}{n_1}, the notation for binomial coefficients. Note that \displaystyle \binom{n}{n_1,n-n_1}=\binom{n}{n_1}.

___________________________________________________________________________

Multinomial Lunch Problem

Viewing the lunch choices as random sampling (each diner randomly chooses from M, B and I), there are 3^{12}= 531,441 many ways can the lunch choices be made for the whole 12-person group. This count contains all the possible choices including possibilities that some restaurant is not chosen. The following is one possible outcome that fall under question 2.

    B-M-B-I-I-M-B-B-M-I-I-I

The above string shows that the first person chooses Burger King, the second person chooses McDonald, the third person chooses Burger King and so on. How many other strings are like this one in the sense that there are 3 M’s, 4 B’s and 5 I’s? This would be a multinomial coefficient.

    \displaystyle \frac{12!}{3! \ 4! \ 5!}=\frac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1 \cdot 4 \cdot 3 \cdot 2 \cdot 1}=\text{27,720}

The answer to the third question is more than 27,720. For example, there could be three diners choosing IN-N-OUT, 4 diners choosing Burger King and 5 diners choosing McDonald. In other words, we need to apply multinomial coefficient on the three positions (three restaurants). There are 6 ways to divide 3 positions resulting in three subsets with one each since \frac{3!}{1! \ 1! \ 1!}=6. Then there are 6 x 27,720 = 166,320 ways for 12 diners making choices so that 3 of them go to one place, 4 of them go to another place and five of them go to the remaining place. This is an example of the double use of the multinomial coefficients – the first application is on dividing the objects into subgroups and the second application on the dividing the subgroups. The following example gives another illustration.

Example 1
A fair die is rolled 15 times. How many of the outcomes consist of four 2’s, five 3’s and six 4’s? How many of the outcomes consist of four of one face, five of another face and six of another face (different from the other two faces)?

The first question is a straight application of one multinomial coefficient.

    \displaystyle \frac{15!}{4! \ 5! \ 6!}=\frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}=\text{630,630}

To understand the second question, consider the notation (0, 4, 5, 6, 0, 0), which means that there are zero 1’s, four 2’s, five 3’s, six 4’s, zero 5’s and zero 6’s from rolling the die 15 times. Basically it shows how many rolls fall into each position (face). Now we are interested in counting other outcomes that have 4, 5 and 6 of another 3 positions. Basically we are trying to divide 6 positions into four groups, one groups with 3 positions that do not appear in the 15 rolls, one groups with one position that appear 4 times, one group with one position that appear 5 times, and one group with one position that appears 6 times. The following shows how many ways to divide the 6 positions.

    \displaystyle \frac{6!}{3! \ 1! \ 1! \ 1!}=120

For each of the 120 times, there are 630,630 outcomes. Thus the answer to the second question is 120 x 630,630 = 75,675,600. \square

___________________________________________________________________________

Multinomial Sampling

We now explore the random sampling angle of multinomial coefficients. To make it easier to follow, we continue to use the Multinomial Lunch Problem. The problem, as discussed above, is like sampling 12 times with replacement from an urn with 3 letters M, B and I. Each of the 12 random selections has 3 outcomes. Thus the experiment in total has 3^{12} = 531,441 outcomes, each of which can be written as a string of 12 letters. Three examples:

    B-M-B-I-I-M-B-B-M-I-I-I

    I-M-M-I-M-M-M-I-M-I-I-M

    M-M-M-M-M-M-M-M-M-M-M-M

These three strings can be called ordered samples for the experiment of randomly selecting from the urn 12 times with replacement. These display the results of each draw sequentially. We can also use unordered samples, which do not contain the orders but contain the number of times each letter is drawn. For the first string, the unordered sample would be (3, 4, 5) where the first number is the number of people choosing McDonald, the second number is the number of people choosing Burger King and the third number is the number of people choosing IN-N-OUT. For the second string, the unordered sample would be (7, 0, 5). For the third, everyone goes to McDonald and so it is (12, 0, 0).

Note that (3, 4, 5) is called an unordered sample because it does not tell us the order of the chosen letters. It only tells us how many times each letter is chosen. The number of ordered samples resulting in an unordered sample would be precisely the multinomial coefficient. For the unordered sample (3, 4, 5), there would be

    \displaystyle \frac{12!}{3! \ 4! \ 5!}=\frac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1 \cdot 4 \cdot 3 \cdot 2 \cdot 1}=\text{27,720}

many ordered samples. In randomly selecting letters 12 times with replacement from an urn containing the letters M, B and I, how many unordered samples are there? To answer this question, it is helpful to look at unordered samples using a star-and-bar diagram. The star-and-bar diagrams for above three unordered samples are:

    * * * | * * * * | * * * * *

    * * * * * * * | \text{ } | * * * * *

    * * * * * * * * * * * * | \text{ } | \text{ }

In the random experiment in question, a star-and-bar diagram has 12 stars, representing the 12 letters selected, and 2 bars, creating three spaces for the three letters M, B and I. In each star-and-bar diagram, there are 12 + 2 = 14 positions, 12 of which are for the stars and the remaining 2 positions are for the bars. In other words, each of the 14 positions can be either a star or a bar. Thus star-and-bar diagrams are the results of a binomial experiment. How many possible star-and-bar diagrams? There are

    \displaystyle \binom{12+2}{11}=\binom{14}{11}=\binom{14}{2}=364

many different diagrams. Thus there are 364 many unordered samples from drawing letters 12 times from an urn containing the letters M, B and I.

A related question is: how many unordered samples are there in this experiments such that each letter is selected at least once? This means that each space in the star-and-bar diagram has at least one star. Then the remaining 12 – 3 = 9 stars will have to be distributed in the three spaces. There are

    \displaystyle \binom{9+2}{9}=\binom{11}{9}=55

unordered samples in which each letter is chosen at least once.

There is another way to interpret the unordered samples. What is the total number of non-negative integer solutions to the equation x + y + x = 12? The solution x = 3, y = 4, z = 5 would be the unordered sample (3, 4, 5). Thus there are 364 different solutions. What is the total number of positive integer solutions to the equation x + y + x = 12? There are 55 such solution. Each such solution would be an unordered sample where each letter is selected at least once.

___________________________________________________________________________

Multinomial Theorem

We now generalize the discussion on multinomial sampling.

Multinomial Sampling

Suppose that a multinomial experiment consisting of n independent trials with each trial resulting in exactly k outcomes is performed. For convenience, these k outcomes are labeled by the symbols x_1,x_2,\cdots,x_k. The result of the experiment can be recorded by an ordered sample, which is a string of n symbols with each symbol being one of x_1,x_2,\cdots,x_k. The result of the experiment can also be recorded by an unordered sample, which is a sequence of k numbers with the first number being the number occurrences of the outcome x_1, the second number being the number of occurrences of the outcome x_2 and so on. The number of possible ordered samples in the multinomial experiment is k^n. The number of ordered samples resulting in a given unordered sample (n_1,n_2,\cdots,n_k) is the multinomial coefficient \displaystyle \binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{n_1! \ n_2! \cdots n_k!}. The number of unordered samples in the experiment is \displaystyle \binom{n+k-1}{n} based on a combinatorial argument using stars and bars. The number of unordered samples such that in each sample, each of the outcomes x_1,x_2,\cdots,x_k occurs at least once is \displaystyle \binom{n-k+k-1}{n-k}=\binom{n-k+k-1}{k-1}=\binom{n-1}{k-1}.

Number of Integer Solutions to Equations

The number of non-negative integer solutions to the equation x_1+x_2+\cdots+x_k=n is \displaystyle \binom{n+k-1}{n}, which is the total number of unordered samples as indicated above. The number of positive integer solutions to the equation x_1+x_2+\cdots+x+k=n is \displaystyle \binom{n-1}{k-1}, which is the number of unordered samples such that each symbol from x_1,x_2,\cdots,x_k occurs at least once in the multinomial sampling.

There is a lot to unpack in the above two paragraphs. It is helpful to follow the random sampling idea on a specific example, either the lunch problem discussed above or another example. The ideas in the above paragraphs contains all the information for stating the multinomial theorem.

Sum of all Multinomial Coefficients

In the multinomial experiment described above, the sum of all possible multinomial coefficients is k^n, i.e. \displaystyle \sum \limits_{a_1+a_2+\cdots a_k=n} \frac{n!}{a_1! \ a_2! \cdots a_k!}=k^n

Multinomial Theorem

The formula shown below shows how to raise a multinomial to a power. \displaystyle (x_1+x_2+\cdots x_k)^n =\sum \limits_{a_1+a_2+\cdots a_k=n} \frac{n!}{a_1! \ a_2! \cdots a_k!} \ x_1^{a_1} x_2^{a_2} \cdots  x_k^{a_k}

The count k^n is identical to the sum of all the possible multinomial coefficients in the experiment. This fact follows from the observations we make about the multinomial sampling. The count k^n is the total number of all ordered samples. The ordered samples can be divided into groups where each group consists of of all ordered samples associating with the same unordered sample. Note that the size of each of these groups is a multinomial coefficient.

The multinomial theorem is a compact way of describing the multinomial experiment. When it is expanded out, the left-hand-side lists out all the k^n ordered samples. A typical ordered sample consists of a_1 many x_1, a_2 many x_2 and so on, which can be represented by x_1^{a_1} x_2^{a_2} \cdots  x_k^{a_k}, which is a term on the right-hand-side. Thus a term such as x_1^{a_1} x_2^{a_2} \cdots  x_k^{a_k} is another way to notate an unordered sample and it represents \frac{n!}{a_1! \ a_2! \cdots a_k!} many ordered samples. Thus \frac{n!}{a_1! \ a_2! \cdots a_k!} x_1^{a_1} x_2^{a_2} \cdots  x_k^{a_k} is the result of aggregating all the ordered samples for a given unordered sample. Summing all these aggregated results give all the possible ordered samples in the multinomial experiment.

___________________________________________________________________________

Examples

The best way to absorb the concepts discussed here is to work excises. Three more examples are presented. Several exercises are given in the section below.

Example 2
Suppose that 11 new hires are assigned to four office locations – the headquarter, branch office North, branch office South and branch office East.

  • How many assignments can be made?
  • How many assignments can be made such that 3 new hires are assigned to the headquarter, 3 new hires are assigned to branch office North, 4 new hires are assigned to branch office South and 1 new hire is assigned to branch office East?
  • How many assignments can be made such that 3 new hires are assigned to one location, 3 new hires are assigned to another location, 4 new hires are assigned to another location and 1 new hire is assigned to the remaining location?

The answer to the first question is 4^{11} = 4,194,304. The answer to the second question is a multinomial coefficient.

    \displaystyle \frac{11!}{3! \ 3! \ 4! \ 1!}=46200

Each assignment can be viewed as a string of 11 letters, each of which is chosen from H, N, S and E (these are the ordered samples discussed above). An unordered sample is a sequence of 4 numbers. For example, the unordered sample for the second question is (3, 3, 4, 1). The third question would include other unordered samples with the numbers summing to 11, e.g. (1, 3, 4, 3). Basically we are trying to divide the 4 letters into 3 groups, one group of one letter appearing once, one group with two letters appearing 3 times each, one group with one letter appearing 4 times. This is another multinomial coefficient.

    \displaystyle \frac{4!}{1! \ 1! \ 2!}=12

Thus the answer to the third question is 12 x 46,200 = 554,400. \square

Example 3
Suppose that 16 new hires are assigned to four office locations – the headquarter, branch office North, branch office South and branch office East. Six of the new hires are engineers and only work in the headquarter or branch office East. The other ten new hires are technicians and can be assigned to any one of the four locations.

  • How many assignments can be made?
  • How many assignments can be made such that four of the engineers will work in the headquarter and two of the new technicians will work in the headquarter, 3 new technicians are assigned to branch office North, 4 new technicians are assigned to branch office South and 1 new technician is assigned to branch office East?
  • How many assignments can be made such that four of the engineers will work in either the headquarter or branch office East and two of the new technicians will work in one of the 4 locations, 3 new technicians are assigned to another location, 4 new technicians are assigned to a third location and 1 new technician is assigned to the remaining location?

There are two assignments, one for engineers and one for technicians. The answer would be obtained by multiplying the two assignment counts. The answer to the first question is 2^6 \cdot 4^{11} = 640,000. The following is the answer to the second question.

    \displaystyle \binom{6}{4} \times \frac{10!}{2! \ 3! \ 4! \ 1!}=15 \times 12600=189000

Note that there are \binom{6}{4} = 15 ways to 4 of the engineers to the headquarter (and thus assigning the other two engineers to the other office). The number of ways to assign 10 technicians to the 4 locations in the indicated numbers is the multinomial coefficient indicated above (the one resulting in 12,600). The following is the answer to the third question.

    \displaystyle \binom{6}{4} \times 2 \times \frac{10!}{2! \ 3! \ 4! \ 1!} \times \frac{4!}{1! \ 1! \ 1! \ 1!}=30 \times 302400=9072000

Note that for the third question, a second multinomial coefficient on the locations is required for each type of workers. \square

Example 4
Fifteen identical brand new mail delivery trucks are assigned to 5 post offices.

  • How many assignments can be made?
  • How many assignments can be made such that each post office is assigned at least one truck?

The problem can be done using the combinatorial argument with stars and bars discussed above. The 15 trucks are stars and there 4 bars creating 5 spaces representing the post offices. Any assignment of trucks would be like a string of 15 stars and 4 bars. The following is an example.

    * * * * | * * * * * * | | * * * * *

The above star-and-bar diagram shows that 4 trucks are assigned to the first post office, 6 trucks are assigned to the second post office, zero trucks are assigned to the third post office and 5 trucks are assigned to the fourth post office. What is more important to notice is that there are 19 positions in the diagram. The problem is to choose 15 of them to place the stars. The following is the answer to the first question.

    \displaystyle \binom{19}{15}=3876

The second question requires that each space has at least one star. We place one star in each space. There are 11 stars left. We now consider 11 stars and 3 bars. The following is the number of ways of arranging 11 stars in 14 positions.

    \displaystyle \binom{14}{11}=364

Thus there are 364 ways to assign 15 trucks to four post offices such that each office gets at least one truck. \square

___________________________________________________________________________

Exercises

Exercise 1
A father is to distribute 9 gifts to his three children.

  1. In how many ways can the gifts be distributed if the eldest child is to receive 2 gifts, the middle child is to receive 2 gifts and the youngest child is to receive 5 gifts?
  2. In how many ways can the gifts be distributed if one child is to receive 2 gifts, another child is to receive 2 gifts and the remaining child is to receive 5 gifts?

Exercise 2
Eleven job assignments are randomly distributed to four workers Marcus, Issac, Samantha and Paul. In how many ways can these jobs be assigned to the four workers such that Marcus will receive one job, Issac will receive 4 jobs, Samantha will receive 4 jobs and Paul will receive 2 jobs?

Exercise 3

  1. Ten students are to be assigned to two math classes. How many ways can the students be divided into the two math classes with 5 students in each class?
  2. Fifteen students are to be assigned to three math classes. How many ways can the students be divided into the three math classes with 5 students in each class?

Exercise 4
An investor has 25 thousand dollars to invest among 5 possible investments. The amount to invest in each investment is in the unit of one thousand dollars. Suppose that the entire amount of 25 thousand dollars is to be invested.

  1. How many different investment strategies are possible?
  2. How many different investment strategies are possible if at least one unit is put into each investment choice?

Exercise 5
Recall the Multinomial Lunch Problem. Each of the twelve people have 3 choices for lunch – McDonald, Burger King and IN-N-OUT, all fast food restaurants. The choice for each person is independent of the choices of the other diners. In how many ways can the lunch choices for this 12-person group be made in such a way that each restaurant is visited by at least 3 diners?

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

Answers

Exercise 1

  1. 756
  2. 2,268

Exercise 2
34,650

Exercise 3

  1. 252
  2. 756,756

Exercise 4

  1. 23,751
  2. 10,626

Exercise 5
256,410
Hint: There are three cases, each of which requires the use of two multinomial coefficients, one for the diners and one for the restaurants.

___________________________________________________________________________
\copyright 2017 – Dan Ma

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s