Page 564 - Discrete Mathematics and Its Applications

8.4 Generating Functions 543

This follows because we obtain a term equal to x 17 in the product by picking a term in the
e 3
e 1
e 2
first sum x , a term in the second sum x , and a term in the third sum x , where the
exponents e 1 ,e 2 , and e 3 satisfy the equation e 1 + e 2 + e 3 = 17 and the given constraints.
It is not hard to see that the coefficient of x 17 in this product is 3. Hence, there are
three solutions. (Note that the calculating of this coefficient involves about as much work
as enumerating all the solutions of the equation with the given constraints. However, the
method that this illustrates often can be used to solve wide classes of counting problems with
special formulae, as we will see. Furthermore, a computer algebra system can be used to
do such computations.) ▲

EXAMPLE 11 In how many different ways can eight identical cookies be distributed among three distinct
children if each child receives at least two cookies and no more than four cookies?

Solution: Because each child receives at least two but no more than four cookies, for each child
there is a factor equal to

3
2
4
(x + x + x )
in the generating function for the sequence {c n }, where c n is the number of ways to distribute n
cookies. Because there are three children, this generating function is

3
4 3
2
(x + x + x ) .
8
8
We need the coefficient of x in this product. The reason is that the x terms in the expansion
correspond to the ways that three terms can be selected, with one from each factor, that have
exponents adding up to 8. Furthermore, the exponents of the term from the first, second, and
third factors are the numbers of cookies the first, second, and third children receive, respectively.
Computation shows that this coefficient equals 6. Hence, there are six ways to distribute the
cookies so that each child receives at least two, but no more than four, cookies. ▲

EXAMPLE 12 Use generating functions to determine the number of ways to insert tokens worth $1, $2,
and $5 into a vending machine to pay for an item that costs r dollars in both the cases when
the order in which the tokens are inserted does not matter and when the order does matter. (For
example, there are two ways to pay for an item that costs $3 when the order in which the tokens
are inserted does not matter: inserting three $1 tokens or one $1 token and a $2 token. When
the order matters, there are three ways: inserting three $1 tokens, inserting a $1 token and then
a $2 token, or inserting a $2 token and then a $1 token.)

Solution: Consider the case when the order in which the tokens are inserted does not matter.
Here, all we care about is the number of each token used to produce a total of r dollars. Because
we can use any number of $1 tokens, any number of $2 tokens, and any number of $5 tokens,
r
the answer is the coefficient of x in the generating function
2
3
4
6
2
5
(1 + x + x + x + ··· )(1 + x + x + x + ··· )(1 + x + x 10 + x 15 + ··· ).
(The first factor in this product represents the $1 tokens used, the second the $2 tokens used, and
the third the $5 tokens used.) For example, the number of ways to pay for an item costing $7
7
using $1, $2, and $5 tokens is given by the coefficient of x in this expansion, which equals 6.
When the order in which the tokens are inserted matters, the number of ways to insert
r
exactly n tokens to produce a total of r dollars is the coefficient of x in
2 5 n
(x + x + x ) ,