Combinations and the Binomial Theorem

We now consider subsets of a given size. How many subsets of a given size can be created from the elements of a given set when order is not a concern? This is a good question when deciding how to partition supply to meet demand when a given number of units are required, without specifying which units.

2.4 Combinations and the Binomial Theorem

2.4.1 Combinations

In Section 2.1 we investigated the most basic concept in combinatorics, namely, the rule of products. It is of paramount importance to keep this fundamental rule in mind. In Section 2.2, we saw a subclass of rule-of-products problems, permutations, and we derived a formula as a computational aid to assist us. In this section, we will investigate another counting formula, one that is used to count combinations, which are subsets of a certain size.

In many rule-of-products applications, the ordering is important, such as the batting order of a baseball team. In other cases it is not important, as in placing coins in a vending machine or in the listing of the elements of a set. Order is important in permutations. Order is not important in combinations.

Example 2.4.1: Counting Permutations. How many different ways are there to permute three letters from the set A = {a, b, c, d}? From the Permutation Counting Formula there are$P(4,3) = \frac{4!}{(4-3)!} = 24$ different orderings of three letters from A.

Example 2.4.2: Counting with No Order. How many ways can we select a set of three letters from A = {a, b, c, d}? Note here that we are not concerned with the order of the three letters. By trial and error, abc, abd, acd, and bcd are the only listings possible. To repeat, we were looking for all three-element subsets of the set A. Order is not important in sets. The notation for choosing 3 elements from 4 is most commonly $\binom{4}{3}$ or occasionally C (4, 3), either of which is read "4 choose 3" or the number of combinations for four objects taken three at a time.

Definition 2.4.3: Binomial Coefficient. Let n and k be non-negative integers. The binomial coefficient $\binom{n}{k}$ represents the number of combinations of n objects taken k at a time, and is read "n choose k". We would now like to investigate the relationship between permutation and combination problems in order to derive a formula for $\binom{n}{k}$

Let us reconsider the Counting with No Order. There are 3! = 6 different orderings for each of the three-element subsets. The table below lists each subset of A and all permutations of each subset on the same line.

subset                 permutations

{a, b, c}               abc, acb, bca, bac, cab, cba

{b, c, d}               bcd, bdc, cdb, cbd, dbc, dcb

Hence, $\binom{4}{3} = \frac{P(4,3)}{3!} = \frac{4!}{(4-3)! \cdot 3!} = 4$

We generalize this result in the following theorem:

Theorem 2.4.4: Binomial Coefficient Formula. If n and k are nonnegative integers with 0 ≤ k ≤ n, then the number k-element subsets of an n element set is equal to

$\binom{n}{k} = \frac{n!}{(n-k)! \cdot k!}$

Proof. Proof 1: There are k! ways of ordering the elements of any k element set. Therefore,

$\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{(n-k)!k!}$

Proof 2: To "construct" a permutation of k objects from a set of n elements, we can first choose one of the subsets of objects and second, choose one of the k! permutations of those objects. By the rule of products,

$P(n,k) = \binom{n}{k} \cdot k!$

and solving for $\binom{n}{k}$ we get the desired formula.

Example 2.4.5: Flipping Coins. Assume an evenly balanced coin is tossed five times. In how many ways can three heads be obtained? This is a combination problem, because the order in which the heads appear does not matter. We can think of this as a situation involving sets by considering the set of flips of the coin, 1 through 5, in which heads comes up. The number of ways to get three heads is $\binom{5}{3} = \frac{5 \cdot 4}{2 \cdot 1} = 10$.

Example 2.4.6: Counting five ordered flips two ways. We determine the total number of ordered ways a fair coin can land if tossed five consecutive times. The five tosses can produce any one of the following mutually exclusive, disjoint events: 5 heads, 4 heads, 3 heads, 2 heads, 1 head, or 0 heads. For example, by the previous example, there are $\binom{5}{3} = 10$ sequences in which three heads appear. Counting the other possibilities in the same way, by the law of addition we have:

$\binom{5}{5} + \binom{5}{4} + \binom{5}{3} + \binom{5}{2} + \binom{5}{1} + \binom{5}{0} = 1 + 5+ 10 + 10 + 5+ 1 = 32$

ways to observe the five flips.

Of course, we could also have applied the extended rule of products, and since there are two possible outcomes for each of the five tosses, we have 25 = 32 ways.

You might think that counting something two ways is a waste of time but solving a problem two different ways often is instructive and leads to valuable insights. In this case, it suggests a general formula for the sum $\sum_{k=0}^{n} \binom{n}{k}$ t he case of n = 5, we get 25 so it is reasonable to expect that the general sum is 2 n, and it is. A logical argument to prove the general statement simply involves generalizing the previous example to n coin flips.

Example 2.4.7: A Committee of Five. A committee usually starts as an unstructured set of people selected from a larger membership. Therefore, a committee can be thought of as a combination. If a club of 25 members has a five-member social committee, there are $\binom{25}{5} = \frac{25 \cdot 24 \cdot 23 \cdot 22 \cdot 21}{5!} = 53130$ different possible social committees. If any structure or restriction is placed on the way the social committee is to be selected, the number of possible committees will probably change. For example, if the club has a rule that the treasurer must be on the social committee, then the number of possibilities is reduced $\binom{24}{4} = \frac{24 \cdot 23 \cdot 22 \cdot 21}{4!} = 10626$.

If we further require that a chairperson other than the treasurer be selected for the social committee, we have $\binom{24}{4} \cdot 4 = 42504$ different possible social committees. The choice of the four non-treasurers accounts for the factor $\binom{24}{4}$ while the need to choose a chairperson accounts for the 4.

Example 2.4.8: Binomial Coefficients - Extreme Cases. By simply applying the definition of a Binomial Coefficient as a number of subsets we see that there is $\binom{n}{0}=1$ way of choosing a combination of zero elements from a set of n. In addition, we see that there is (n) = 1 way of choosing a combination of n elements from a set of n.

We could compute these values using the formula we have developed, but no arithmetic is really needed here. Other properties of binomial coefficients that can be derived using the subset definition will be seen in the exercises.

2.4.2 The Binomial Theorem

The binomial theorem gives us a formula for expanding (x + y)n, where n is a nonnegative integer. The coefficients of this expansion are precisely the binomial coefficients that we have used to count combinations. Using high school algebra we can expand the expression for integers from 0 to 5:

n                                   (x + y)n

0                                         1

1                                     x + y

2                             x2 + 2xy + y2

3                      x3 + 3x2y + 3xy2 + y3

4              x4 + 4x3y + 6x2y2 + 4xy3 + y4

5    x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5

In the expansion of (x + y)5 we note that the coefficient of the third term is $\binom{5}{3} = 10$, and that of the sixth term is $\binom{5}{3} = 10$. We can rewrite the expansion

$\binom{5}{0}x^5 + \binom{5}{1}x^4y + \binom{5}{2}x^3y^2 + \binom{5}{3}x^2y^3 + \binom{5}{4}xy^4 + \binom{5}{5}y^5$

In summary, in the expansion of (x + y) n we note:

(a) The first term is xn and the last term is yn .

(b) With each successive term, exponents of x decrease by 1 as those of y increase by 1. For any term the sum of the exponents is n.

(c) The coefficient of xnkyk is $\binom{n}{k}$

(d) The triangular array of binomial coefficients is called Pascal's triangle after the seventeenth-century French mathematician Blaise Pascal. Note that each number in the triangle other than the 1's at the ends of each row is the sum of the two numbers to the right and left of it in the row above.

Theorem 2.4.9: The Binomial Theorem. If n 0, and x and y are numbers, then

$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$

Proof. This theorem will be proven using a logical procedure called mathematical induction, which will be introduced in Chapter 3.

Example 2.4.10: Identifying a term in an expansion. Find the third term in the expansion of (x − y)4 = (x + ( −y))4. The third term, when k = 2, is $\binom{4}{2} x^{4-2} (-y)^2 = 6x^2y^2$.

Example 2.4.11: A Binomial Expansion. Expand (3x − 2)3. If we replace x and y in the Binomial Theorem with 3x and −2, respectively, we get

$\sum_{k=0}^{3} \binom{3}{k} (3x)^{n-k}(-2)^k = \binom{3}{0}(3x)^3(-2)^0 + \binom{3}{1}(3x)^2(-2)^1 + \binom{3}{2}(3x)^1(-2)^2 + \binom{3}{3}(3x)^0(-2)^3 = 27x^3 - 54x^2 + 36x - 8$