Page 436 - Discrete Mathematics and Its Applications

6.4 Binomial Coefficients and Identities 415

39. How many license plates consisting of three letters fol- medals, and the runner or runners who finish with exactly
lowed by three digits contain no letter or digit twice? two runners ahead receive bronze medals.)
A circular r-permutation of n people is a seating of r of ∗ 46. This procedure is used to break ties in games in the cham-
these n people around a circular table, where seatings are con- pionship round of theWorld Cup soccer tournament. Each
sidered to be the same if they can be obtained from each other team selects five players in a prescribed order. Each of
by rotating the table. these players takes a penalty kick, with a player from the
40. Find the number of circular 3-permutations of 5 people. first team followed by a player from the second team and
so on, following the order of players specified. If the score
41. Find a formula for the number of circular r-permutations
of n people. is still tied at the end of the 10 penalty kicks, this proce-
dure is repeated. If the score is still tied after 20 penalty
42. Findaformulaforthenumberofwaystoseat r ofnpeople
kicks, a sudden-death shootout occurs, with the first team
around a circular table, where seatings are considered the scoring an unanswered goal victorious.
same if every person has the same two neighbors without
regard to which side these neighbors are sitting on. a) How many different scoring scenarios are possible if
the game is settled in the first round of 10 penalty
43. How many ways are there for a horse race with three
kicks, where the round ends once it is impossible for
horses to finish if ties are possible? [Note: Two or three a team to equal the number of goals scored by the
horses may tie.]
other team?
∗ 44. How many ways are there for a horse race with four horses b) How many different scoring scenarios for the first
to finish if ties are possible? [Note: Any number of the and second groups of penalty kicks are possible if
four horses may tie.) the game is settled in the second round of 10 penalty
∗ 45. There are six runners in the 100-yard dash. How many kicks?
ways are there for three medals to be awarded if ties c) How many scoring scenarios are possible for the full
are possible? (The runner or runners who finish with the set of penalty kicks if the game is settled with no more
fastest time receive gold medals, the runner or runners than 10 total additional kicks after the two rounds of
who finish with exactly one runner ahead receive silver five kicks for each team?

6.4 Binomial Coefficients and Identities

As we remarked in Section 6.3, the number of r-combinations from a set with n elements is
n

often denoted by . This number is also called a binomial coefficient because these numbers
r
n
occur as coefficients in the expansion of powers of binomial expressions such as (a + b) .We
will discuss the binomial theorem, which gives a power of a binomial expression as a sum of
terms involving binomial coefficients. We will prove this theorem using a combinatorial proof.
We will also show how combinatorial proofs can be used to establish some of the many different
identities that express relationships among binomial coefficients.

The Binomial Theorem

The binomial theorem gives the coefficients of the expansion of powers of binomial expressions.
A binomial expression is simply the sum of two terms, such as x + y. (The terms can be products
of constants and variables, but that does not concern us here.)
Example 1 illustrates how the coefficients in a typical expansion can be found and prepares
us for the statement of the binomial theorem.
3
EXAMPLE 1 The expansion of (x + y) can be found using combinatorial reasoning instead of multiplying
3
the three terms out. When (x + y) = (x + y)(x + y)(x + y) is expanded, all products of a
term in the first sum, a term in the second sum, and a term in the third sum are added. Terms of
3
2
3
3
2
the form x , x y, xy , and y arise. To obtain a term of the form x ,an x must be chosen in
3
each of the sums, and this can be done in only one way. Thus, the x term in the product has
2
a coefficient of 1. To obtain a term of the form x y,an x must be chosen in two of the three
sums (and consequently a y in the other sum). Hence, the number of such terms is the number
3
2
of 2-combinations of three objects, namely, . Similarly, the number of terms of the form xy
2
is the number of ways to pick one of the three sums to obtain an x (and consequently take a y