CS202: Discrete Structures

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

{a, b, d}               abd, adb, bda, bad, dab, dba

{a, c, d}               acd, adc, cda, cad, dac, dca

{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

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 2⁵ = 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 2⁵ so it is reasonable to expect that the general sum is 2 ⁿ, 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)ⁿ, 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)ⁿ

0                                         1

1                                     x + y

2                             x² + 2xy + y²

3                      x³ + 3x²y + 3xy² + y³

4              x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴

5    x⁵ + 5x⁴y + 10x³y² + 10x²y³ + 5xy⁴ + y⁵

In the expansion of (x + y)⁵ 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) ⁿ we note:

(a) The first term is xⁿ and the last term is yⁿ .

(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 x^n−ky^k 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

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)⁴ = (x + ( −y))⁴. 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)³. 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$