This is the third post in a series of posts on combinatorial analysis. The post is opened with the following 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.
First we highlight the important concepts introduced in the previous post on permutations and combinations.
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.
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 .
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 .
Other notations for the binomial coefficient are , and . 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 . 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.
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.
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 .
Several Interpretations of the Binomial Coefficients
The path problem makes it clear that there are several ways of looking at the binomial coefficient . Each of the following is a count that is computed by .
- The number of different groups of size that can be chosen from a set of objects.
- The number of ways a set of objects can be labeled by 0 or 1.
- The number of different -character strings that can be formed by using of one symbol and of another symbol.
- The number of permutations of items, of which are alike and are alike.
- A random experiment consists of 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 of the trials result in outcome 1 and of the trials result in outcome 2.
- An urn contains a large number of balls, each of which is labeled 0 or 1. Randomly select a ball times from the urn with replacement. The number of ways the balls can be selected in such a way that of the balls are labeled 1 and 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 , according to idea 1, would be the number of all possible subsets of size that can be chosen from a set of objects. We can also think of choosing a subset as a random experiment of trials where each trial has two distinct outcomes. Out of the objects, we only want of them with . Then for each object, there is a decision – choose it or not choose it (two distinct outcomes). So there are 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 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 decisions successively is like a string of 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 , is called a binomial. The binomial theorem is a formula for deriving the power of a binomial, i.e. for deriving for . 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.
The above derivations are deliberately detailed to make a point. For example, the result of is product of 5 identical factors of . Multiplying out these five factors of results in 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:
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 .
In general, is obtained by multiplying factors of . In the expansion, a typical term is , which can be viewed as a -letter string of of the letters are and of the letters are . We can also look at the situation as choosing of the positions to write the letter y. There are many ways of writing instances of y in positions. Thus would be one of the terms in the final result of the expansion. This is the reason why is referred to as binomial coefficients.
A Recursive Formula
The combination 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.
The formula can be derived by the following thought process. A -subset of a set of objects is a subset consisting of exactly elements. The quantity is the number of -subsets of a set of objects. For our purpose here, the objects are the numbers . Let fix one of the objects, say 1. There are two types of -subsets – the ones containing 1 and the ones not containing 1. The number of -subsets of the first type is . The point 1 is known to be in each -subset of the first type and the other points must be chosen from objects. The number of -subsets of the second type is . The point 1 is not in each -subset of the second type. So all are chosen from the other objects. Thus is the sum of these two numbers.
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.
Each row in the triangle gives the binomial coefficients in the expansion , starting at . Thus the second row gives the coefficients for the expansion of , the third row gives the coefficients for 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 . 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 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 . The cell directly above it is . The cell to the left of that one is .
How Many Subsets Are There of a Given Set?
Given objects, we now know that there are many sets of elements from these objects. There are 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 and . Write out the binomial theorem. The following is the result.
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 . 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.
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.
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?
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?
- 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?