Page 562 - Discrete Mathematics and Its Applications

8.4 Generating Functions 541

−n
Using Example 8, which provides a simple formula for , we obtain
k
∞

k
k
(1 + x) −n = (−1) C(n + k − 1,k)x .
k = 0
Replacing x by −x, we find that

∞

−n k
(1 − x) = C(n + k − 1,k)x .
k = 0 ▲
Table 1 presents a useful summary of some generating functions that arise frequently.

Remark: Note that the second and third formulae in this table can be deduced from the first
r
formula by substituting ax and x for x, respectively. Similarly, the sixth and seventh formulae
can be deduced from the fifth formula using the same substitutions. The tenth and eleventh can
be deduced from the ninth formula by substituting −x and ax for x, respectively. Also, some
of the formulae in this table can be derived from other formulae using methods from calculus
(such as differentiation and integration). Students are encouraged to know the core formulae in
this table (that is, formulae from which the others can be derived, perhaps the first, fourth, fifth,
eighth, ninth, twelfth, and thirteenth formulae) and understand how to derive the other formulae
from these core formulae.

Counting Problems and Generating Functions

Generating functions can be used to solve a wide variety of counting problems. In particular, they
can be used to count the number of combinations of various types. In Chapter 6 we developed
techniques to count the r-combinations from a set with n elements when repetition is allowed
and additional constraints may exist. Such problems are equivalent to counting the solutions to
equations of the form

e 1 + e 2 + ··· + e n = C,

where C is a constant and each e i is a nonnegative integer that may be subject to a specified
constraint. Generating functions can also be used to solve counting problems of this type, as
Examples 10–12 show.

EXAMPLE 10 Find the number of solutions of

e 1 + e 2 + e 3 = 17,

where e 1 ,e 2 , and e 3 are nonnegative integers with 2 ≤ e 1 ≤ 5, 3 ≤ e 2 ≤ 6, and 4 ≤ e 3 ≤ 7.

Solution: The number of solutions with the indicated constraints is the coefficient of x 17 in the
expansion of

2
5
4
6
7
3
4
3
5
4
6
5
(x + x + x + x )(x + x + x + x )(x + x + x + x ).