Page 566 - Discrete Mathematics and Its Applications

8.4 Generating Functions 545

EXAMPLE 14 Use generating functions to find the number of r-combinations from a set with n elements when
repetition of elements is allowed.

Solution: Let G(x) be the generating function for the sequence {a r }, where a r equals the number
∞ r

a
ofr-combinationsofasetwithnelementswithrepetitionsallowed.Thatis,G(x) = r = 0 r x .
Because we can select any number of a particular member of the set with n elements
when we form an r-combination with repetition allowed, each of the n elements contributes
3
2
(1 + x + x + x + ··· ) to a product expansion for G(x). Each element contributes this factor
because it may be selected zero times, one time, two times, three times, and so on, when an
r-combination is formed (with a total of r elements selected). Because there are n elements in
the set and each contributes this same factor to G(x),wehave

2
n
G(x) = (1 + x + x + ··· ) .
2
As long as |x| < 1, we have 1 + x + x + ··· = 1/(1 − x),so

n
G(x) = 1/(1 − x) = (1 − x) −n .

Applying the extended binomial theorem (Theorem 2), it follows that

∞
−n r
−n
−n
(1 − x) = (1 + (−x)) = (−x) .
r
r = 0
The number of r-combinations of a set with n elements with repetitions allowed, when r is a
r
positive integer, is the coefficient a r of x in this sum. Consequently, using Example 8 we find
that a r equals

−n r r r
(−1) = (−1) C(n + r − 1,r) · (−1)
r
= C(n + r − 1,r). ▲

Note that the result in Example 14 is the same result we stated as Theorem 2 in Section 6.5.

EXAMPLE 15 Use generating functions to find the number of ways to select r objects of n different kinds if
we must select at least one object of each kind.

Solution: Because we need to select at least one object of each kind, each of the n kinds of objects
2
3
contributes the factor (x + x + x + ··· ) to the generating function G(x) for the sequence {a r },
where a r is the number of ways to select r objects of n different kinds if we need at least one
object of each kind. Hence,

2 3 n n 2 n n n
G(x) = (x + x + x + ··· ) = x (1 + x + x + ··· ) = x /(1 − x) .