Page 565 - Discrete Mathematics and Its Applications

544 8 / Advanced Counting Techniques

because each of the r tokens may be a $1 token, a $2 token, or a $5 token. Because any number
of tokens may be inserted, the number of ways to produce r dollars using $1, $2, or $5 tokens,
r
when the order in which the tokens are inserted matters, is the coefficient of x in

1
2 5 2 5 2
1 + (x + x + x ) + (x + x + x ) + ··· =
5
2
1 − (x + x + x )
1
= ,
2
1 − x − x − x 5
where we have added the number of ways to insert 0 tokens, 1 token, 2 tokens, 3 tokens, and
2
so on, and where we have used the identity 1/(1 − x) = 1 + x + x + ··· with x replaced
2
5
with x + x + x . For example, the number of ways to pay for an item costing $7 using $1, $2,
7
and $5 tokens, when the order in which the tokens are used matters, is the coefficient of x in this
expansion, which equals 26. [Hint: To see that this coefficient equals 26 requires the addition
5 k
2
7
of the coefficients of x in the expansions (x + x + x ) for 2 ≤ k ≤ 7. This can be done by
hand with considerable computation, or a computer algebra system can be used.] ▲
Example 13 shows the versatility of generating functions when used to solve problems with
differing assumptions.
EXAMPLE 13 Use generating functions to find the number of k-combinations of a set with n elements.Assume
that the binomial theorem has already been established.

Solution: Each of the n elements in the set contributes the term (1 + x) to the generating function
n k
a
f(x) = k = 0 k x . Here f(x) is the generating function for {a k }, where a k represents the
number of k-combinations of a set with n elements. Hence,
n
f(x) = (1 + x) .

But by the binomial theorem, we have

n
n k
f(x) = x ,
k
k = 0
where

n n!
= .
k k!(n − k)!

Hence, C(n, k), the number of k-combinations of a set with n elements, is

n!
.
k!(n − k)! ▲

Remark: We proved the binomial theorem in Section 6.4 using the formula for the number of
r-combinations of a set with n elements. This example shows that the binomial theorem, which
can be proved by mathematical induction, can be used to derive the formula for the number of
r-combinations of a set with n elements.