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}

Advertisements

3 thoughts on “Binomial coefficients

  1. Pingback: Multinomial coefficients | All Math Considered

  2. Pingback: How to calculate winning odds in Powerball | All Math Considered

  3. Pingback: The probabilities of poker hands | All Math Considered

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