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

Binomial coefficients

This is the third post in a series of posts on combinatorial analysis. The post is opened with the following problem.

    Figure 1
    path-problem

Path Problem
Point Q is 7 blocks east and 6 blocks north of Point P (see Figure 1). A person wants to walk from Point P to Point Q by walking 13 blocks. Assume that all the paths from any point to any point in the above diagram are available for walking. In how many ways can the person go from Point P to Point Q?

One way to solve this problem is to count the number of paths in a “brute force” approach by tracing all possible paths in the diagram. The total number of paths is 1,716. So counting directly is not a practical approach. It turns out that the path problem and other similar problems will become routine once the concept of binomial coefficients is clearly understood.

___________________________________________________________________________

Review

First we highlight the important concepts introduced in the previous post on permutations and combinations.

The number n!, read n factorial, is defined by the product n!=n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1. It is the number of ordered arrangements of n objects.

For convenience we define 0! = 1. An ordered arrangement of a set of objects is called a permutation. How many permutations are there of 7 objects? For example, how many ways can the following 7 people be arranged in a row for a group photo: Abby, Beth, Charlie, David, Edward, Frank, and George? An equivalent question: how many permutations are there of the letters A, B, C, D, E, F and G? The answer is 7! = 5040. The reasoning is based on the multiplication principle (see here). There are 7 people to choose for the first position, and there are 6 people to choose from for the second position after the first position is fixed, and so on. Thus there are 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040.

The number of permutations of k objects chosen from n objects is defined by \displaystyle P(n,k)=\frac{n!}{(n-k)!}.

Out of the 7 people mentioned above, how many ways can three people be randomly selected to receive three cash prizes of $1000, $500 and $100? An equivalent question: how many permutations are there of 3 letters chosen from the 7 letters A, B, C, D, E, F and G? The answer can also be obtained by the multiplication principle. There are 7 x 6 x 5 = 210 permutations, which is identical to P(7,3)=\frac{7!}{(7-3)!}=\frac{7!}{4!}=7 \times 6 \times 5.

The number of different groups of size k that can be chosen from a set of n distinct objects is \displaystyle \binom{n}{k}=\frac{n!}{k! \ (n-k)!} where n is a positive integer and k=0,1,2,\cdots,n. This number is called the number of possible combinations of n objects chosen k at a time. The values \displaystyle \binom{n}{k} are often referred to as binomial coefficients because of their connection with the binomial theorem.

Out of the 7 people mentioned above, how many ways can three people be randomly selected to receive three cash prizes, each of which is $1000? An equivalent question: how many three-letter sets can be chosen from the 7 letters A, B, C, D, E, F and G? Here, the order does not matter. The answer 210 obtained previously is too large because it contains many repeats. For example, the letters A, B and C has 3! = 6 permutations. In the answer 210, each 3-letter combination occurs 6 times. So the answer is 210 / 6 = 35, which is identical to \binom{7}{3}=35.

Other notations for the binomial coefficient \binom{n}{k} are _nC_k, C(n,k) and C_{n,k}. Permutation and combination can all be computed directly in terms of factorials. The calculation can also be done using calculator or software. Most calculators have functions for combination (binomial coefficient) and permutation. In Excel, the binomial coefficient is computed by the formula =COMBIN(n, k), which will give the result as \binom{n}{k}. The Excel formula for permutation is =PERMUT(n,k).

___________________________________________________________________________

The Path Problem

Recall that the problem is to walk 7 blocks East and 6 blocks North starting at point P. Let use E to mean walking one block East and N to mean walking one block North. The following is one specific path that the person might take.

    Figure 2
    path-problem-specific-path

The path in Figure 2 can be described by the string E-E-N-N-N-E-N-E-E-E-N-N-E. Of course there are many other possible paths that can be taken. Observe that each possible path correspond to a string of 7 E’s and 6 N’s. On the other hand, each possible 13-character string with 7 E’s and 6 N’s correspond to a path in the problem. So the problem is about finding the number of possible 13-character string with 7 E’s and 6 N’s. In other words, we are in interested in all the ways we can write 7 E’s and 6 N’s in the following 13 positions.

    \LARGE \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box

Writing 7 E’s and 6 N’s in 13 boxes is the same as choosing 7 boxes out of 13 boxes to fill with 7 E’s. The number of ways to choose 7 objects out of 13 objects is simply \binom{13}{7}=1716.

___________________________________________________________________________

Several Interpretations of the Binomial Coefficients

The path problem makes it clear that there are several ways of looking at the binomial coefficient \displaystyle \binom{n}{k}. Each of the following is a count that is computed by \displaystyle \binom{n}{k}.

  1. The number of different groups of size k that can be chosen from a set of n objects.
  2. The number of ways a set of n objects can be labeled by 0 or 1.
  3. The number of different n-character strings that can be formed by using k of one symbol and n-k of another symbol.
  4. The number of permutations of n items, of which k are alike and n-k are alike.
  5. A random experiment consists of n trials, each of which results in one of two outcomes (outcome 1 and outcome 2). The number of ways the experiment can be performed such that k of the trials result in outcome 1 and n-k of the trials result in outcome 2.
  6. An urn contains a large number of balls, each of which is labeled 0 or 1. Randomly select a ball n times from the urn with replacement. The number of ways the balls can be selected in such a way that k of the balls are labeled 1 and n-k of the balls are labeled 0.

The same theme runs through the above 6 ideas. The first one is the standard definition of binomial coefficient. The number \binom{n}{k}, according to idea 1, would be the number of all possible subsets of size k that can be chosen from a set of n objects. We can also think of choosing a subset as a random experiment of n trials where each trial has two distinct outcomes. Out of the n objects, we only want k of them with k \le n. Then for each object, there is a decision – choose it or not choose it (two distinct outcomes). So there are n trials and each trial has two outcomes (idea 5). We can also think of a random sampling process too. Perform each trial that ends in two outcomes will be like a random sampling from a population consisting of 0’s and 1’s (idea 6).

Going back to the n objects in idea 1, deciding whether to choose each object is also like labeling that object with 0 or 1 (idea 2). Since each object generates two outcomes (choose or not choose), the n decisions successively is like a string of n characters, each of which is one of two distinct symbols (ideas 3 and 4).

Though the interpretation may be nuanced, the calculation of the binomial coefficient is straightforward. Thinking of the binomial coefficient as the number of ways to making a series of two-outcome decisions is crucial to the understanding of binomial distribution. In the remainder of the post, we discuss other properties of the binomial coefficients.

___________________________________________________________________________

The Binomial Theorem

The sum of two symbols, say x+y, is called a binomial. The binomial theorem is a formula for deriving the power of a binomial, i.e. for deriving (x+y)^n for n=1,2,3,\cdots. We explain the idea behind the formula. The ideas 3 and 4 discussed above are particularly useful ways of looking at the binomial theorem. Consider the first several expansions.

    \displaystyle \begin{aligned} (x+y)^1&=x+y  \end{aligned}

    \displaystyle \begin{aligned} (x+y)^2&=(x+y) (x+y)\\&=xx+xy+yx+yy \\&=x^2+2xy+y^2 \end{aligned}

    \displaystyle \begin{aligned} (x+y)^3&=(x+y) (x+y) (x+y)\\&=xxx+xxy+xyx+yxx+xyy+yxy+yyx+yyy \\&=x^3+3x^2y^1+3xy^2+y^3  \end{aligned}

    \displaystyle \begin{aligned} (x+y)^4&=(x+y) (x+y) (x+y) (x+y)\\&=xxxx+xxxy+xxyx+xyxx+yxxx\\& \ \ +xxyy+ xyxy+xyyx+yxxy+yxyx+yyxx\\&\ \ +xyyy+yxyy+yyxy+yyyx+yyyy \ \ \ \ \ \ \ \ \ \text{(16 terms)} \\&=x^4+4x^3y^1+6x^2y^2+4xy^3+y^4  \end{aligned}

    \displaystyle \begin{aligned} (x+y)^5&=(x+y) (x+y) (x+y) (x+y) (x+y)\\&=xxxxx+xxxxy+xxxyx+xxyxx+xyxxx+yxxxx \cdots \\& \ \ +xxxyy+xxyxy+xyxxy+yxxxy+xxyyx \\& \ \ + xyxyx+yxxyx+xyyxx+yxyxx+yyxxx \ \ + \cdots (\text{32 terms}) \\&=x^5+5x^4y^1+10x^3y^2+10x^2y^3+5xy^4+y^5  \end{aligned}

The above derivations are deliberately detailed to make a point. For example, the result of (x+y)^5 is product of 5 identical factors of x+y. Multiplying out these five factors of x+y results in 2^5=32 terms. Each of these 32 items is a string of x’s and y’s. Let’s look at the strings with 3 x’s and 2 y’s. they are:

    xxxyy+xxyxy+xyxxy+yxxxy+xxyyx

    xyxyx+yxxyx+xyyxx+yxyxx+yyxxx

To find out how many such strings are possible, we need to find out the number of 5-letter strings of which 3 letters are the same and the other 2 letters are the same. That would be \binom{5}{3}=\binom{5}{2}=10.

In general, (x+y)^n is obtained by multiplying n factors of x+y. In the expansion, a typical term is x^{n-j} y^j, which can be viewed as a n-letter string of n-j of the letters are x and j of the letters are y. We can also look at the situation as choosing j of the n positions to write the letter y. There are \binom{n}{j} many ways of writing j instances of y in n positions. Thus \binom{n}{j} x^{n-j} y^j would be one of the terms in the final result of the expansion. This is the reason why \binom{n}{j} is referred to as binomial coefficients.

The binomial theorem shows how to derive the power of a binomial. The formula is: \displaystyle (x+y)^n=\binom{n}{0} x^n+\binom{n}{1} x^{n-1}y^1+\binom{n}{2} x^{n-2}y^2+\cdots+\binom{n}{j} x^{n-j}y^j+\cdots+\binom{n}{n-1} x^{1}y^{n-1}+\binom{n}{n} y^n.

A more compact way of stating the binomial theorem is: \displaystyle (x+y)^n=\sum \limits_{j=1}^n \binom{n}{j} x^{n-j}y^j.

___________________________________________________________________________

A Recursive Formula

The combination \displaystyle \binom{n}{k} can be evaluated using calculator or software. We may not need the following formula for the purpose of calculation. However, it does provide a great deal of insight.

    \displaystyle \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}

The formula can be derived by the following thought process. A k-subset of a set of n objects is a subset consisting of exactly k elements. The quantity \displaystyle \binom{n}{k} is the number of k-subsets of a set of n objects. For our purpose here, the n objects are the numbers 1,2,3,\cdots,n. Let fix one of the objects, say 1. There are two types of k-subsets – the ones containing 1 and the ones not containing 1. The number of k-subsets of the first type is \displaystyle \binom{n-1}{k-1}. The point 1 is known to be in each k-subset of the first type and the other k-1 points must be chosen from n-1 objects. The number of k-subsets of the second type is \displaystyle \binom{n-1}{k}. The point 1 is not in each k-subset of the second type. So all k are chosen from the other n-1 objects. Thus \displaystyle \binom{n}{k} is the sum of these two numbers.

___________________________________________________________________________

Pascal’s Triangle

No discussion of the binomial coefficients is complete without mentioning the Pascal’s triangle. The triangle is usually represented as an isosceles triangle (or an equilateral triangle). We use a right angle representation.

\begin{array}{rrrrrrrrr}      1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }    \\ 1 & 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }   \\ 1 & 2 & 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }   \\ 1 & 3 & 3 & 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }  \\ 1 & 4 & 6 & 4 & 1 & \text{ } & \text{ } & \text{ } & \text{ }  \\ 1 & 5 & 10 & 10 & 5 & 1 & \text{ } & \text{ } & \text{ }  \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & \text{ } & \text{ }  \\ 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 & \text{ }  \\ 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1        \end{array}

Each row in the triangle gives the binomial coefficients in the expansion (x+y)^n, starting at n=0. Thus the second row gives the coefficients for the expansion of (x+y)^1, the third row gives the coefficients for (x+y)^2 and so on. The most interesting part about the triangle is that it is recursive. Each row is derived from the previous row.

Each cell in a row is the sum of the two cells in the row above it – the cell directly above and the cell to the left of that. For example, the last row in the above triangle shows the coefficients for (x+y)^8. The third number from the left is 28, which is the sum of 21 and 7. The fourth element 56 is the sum of 35 (the cell directly above it) and 21 (the cell to the left of 35). As a result, any row can be derived from the previous row. The next row will be for (x+y)^9 have the following coefficients:

    1, 9, 36, 84, 126, 126, 84, 36, 9, 1

The Pascal’s triangle is really the recursive formula discussed above. A typical cell in the triangle is the binomial coefficient \binom{n}{k}. The cell directly above it is \binom{n-1}{k}. The cell to the left of that one is \binom{n-1}{k-1}.

___________________________________________________________________________

How Many Subsets Are There of a Given Set?

Given n objects, we now know that there are \binom{n}{k} many sets of k elements from these n objects. There are \binom{7}{3}=35 many sets of 3 letters from the letters C, K, M, L, T, P and O. There are several ways to come up with the answer.

One way is to use the binomial theorem. Let x=y=1 and n=7. Write out the binomial theorem. The following is the result.

    \displaystyle 128=2^7=(1+1)^7=\binom{7}{0}+\binom{7}{1}+\binom{7}{2}+\binom{7}{3}+\binom{7}{4}+\binom{7}{5}+\binom{7}{6}+\binom{7}{7}

There are 128 different subsets of the 7 letters (or any other set of 7 objects). The reason is given in the right side of the above equation, which is the sum of the number of subsets with zero elements, plus the number of subsets with exactly one element, plus the number of subsets with exactly two elements, …, plus the number of subsets with seven elements.

When buying a hamburger at a fast food restaurant, customers can always add toppings. A basic hamburger comes with a beef patty inside a bun. A customer can choose to add toppings from this list: Cheese, Ketchup, Mustard, Lettuce, Tomato, Pickles and Onion (compare the first letters with the 7 letters indicated earlier). How many different hamburgers can be created? Basically the problem is to find out the number of different subsets of the 7 letters C, K, M, L, T, P and O. The answer is of course 2^7=128. Interestingly the answer of 128 includes one choice that is the plain burger with no toppings – just the beef and the bun. So the total number of different hamburgers with at least one topping would be 127.

In general, the total number of subsets of a set with n elements is 2^n. This is confirmed by the plugging x=1 and y=1 into the binomial theorem: \displaystyle 2^n=(1+1)^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\binom{n}{3}+\cdots+\binom{n}{n-1}+\binom{n}{n}

___________________________________________________________________________

Exercises

Exercise 1
Starting at Point P, a student walks 6 blocks to a diner for breakfast (represented by the red dot in the following diagram). After breakfast, the students 7 blocks to school that is located at Point Q. In how many ways can the student walk from Point P to Point Q? Assume that all the paths from any point to any point in the above diagram are available for walking.

    Figure 2

Exercise 2
In ordering a pizza, a customer can choose from a list of 10 toppings: mushroom, onion, olive, bell pepper, pineapple, spinach, extra cheese, sausage, ham, and pepperoni.

  • How many different pizza can the customer create if any topping in the list is desirable to the customer and if the customer chooses at least one topping?
  • Suppose that the customer is a meat lover. He will always choose the three meat toppings: sausage, ham and pepperoni. He will also choose up to 3 vegetable toppings. How many different pizza can the customer create?

Exercise 3
A committee of 8 people is to be chosen from a class consisting of 8 men and 9 women. If the committee must consist of at least 3 men and at least 4 women, how many different committees are possible?

Exercise 4

  • In how many ways can a father divide 8 gifts among his two children if the eldest is to receive 5 gifts and the other child 3 gifts?
  • In how many ways can a father divide 8 gifts among his two children if one child is to receive 5 gifts and the other child 3 gifts?

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

Answers

Exercise 1
315

Exercise 2

  • 1023
  • 792

Exercise 3
15876

Exercise 4

  • 56
  • 112

___________________________________________________________________________
\copyright \ 2017 \text{ by Dan Ma}