Page 571 - Discrete Mathematics and Its Applications

550 8 / Advanced Counting Techniques

16. Use generating functions to find the number of ways to b) Use part (a) to find the number of ways to roll a total
choose a dozen bagels from three varieties—egg, salty, of 8 when a die is rolled repeatedly, and the order of
and plain—if at least two bagels of each kind but no more the rolls matters. (Use of a computer algebra package
than three salty bagels are chosen. is advised.)
17. In how many ways can 25 identical donuts be distributed 27. Use generating functions (and a computer algebra pack-
to four police officers so that each officer gets at least age, if available) to find the number of ways to make
three but no more than seven donuts? change for $1 using
18. Use generating functions to find the number of ways to a) dimes and quarters.
select 14 balls from a jar containing 100 red balls, 100 b) nickels, dimes, and quarters.
blue balls, and 100 green balls so that no fewer than 3 and c) pennies, dimes, and quarters.
no more than 10 blue balls are selected. Assume that the d) pennies, nickels, dimes, and quarters.
order in which the balls are drawn does not matter. 28. Use generating functions (and a computer algebra pack-
19. What is the generating function for the sequence {c k }, age, if available) to find the number of ways to make
where c k is the number of ways to make change for k change for $1 using pennies, nickels, dimes, and quarters
dollars using $1 bills, $2 bills, $5 bills, and $10 bills? with
20. What is the generating function for the sequence {c k }, a) no more than 10 pennies.
where c k represents the number of ways to make change b) no more than 10 pennies and no more than 10 nickels.
for k pesos using bills worth 10 pesos, 20 pesos, 50 pesos, ∗ c) no more than 10 coins.
and 100 pesos? 29. Use generating functions to find the number of ways to
21. Give a combinatorial interpretation of the coefficient make change for $100 using
4
3
2
3
of x in the expansion (1 + x + x + x + ··· ) . Use a) $10, $20, and $50 bills.
this interpretation to find this number.
b) $5, $10, $20, and $50 bills.
22. Give a combinatorial interpretation of the coefficient c) $5, $10, $20, and $50 bills if at least one bill of each
6
3
2
n
of x in the expansion (1 + x + x + x + ··· ) . Use denomination is used.
this interpretation to find this number. d) $5, $10, and $20 bills if at least one and no more than
four of each denomination is used.
23. a) What is the generating function for {a k }, where a k
is the number of solutions of x 1 + x 2 + x 3 = k when 30. If G(x) is the generating function for the sequence {a k },
x 1 ,x 2 , and x 3 are integers with x 1 ≥ 2, 0 ≤ x 2 ≤ 3, what is the generating function for each of these se-
and 2 ≤ x 3 ≤ 5? quences?
b) Use your answer to part (a) to find a 6 .
a) 2a 0 ,2a 1 ,2a 2 ,2a 3 , ...
24. a) What is the generating function for {a k }, where a k b) 0, a 0 , a 1 , a 2 , a 3 , ... (assuming that terms follow the
is the number of solutions of x 1 + x 2 + x 3 + x 4 = k
pattern of all but the first term)
when x 1 , x 2 , x 3 , and x 4 are integers with x 1 ≥ 3,
c) 0, 0, 0, 0, a 2 , a 3 , ... (assuming that terms follow the
1 ≤ x 2 ≤ 5, 0 ≤ x 3 ≤ 4, and x 4 ≥ 1?
pattern of all but the first four terms)
b) Use your answer to part (a) to find a 7 .
d) a 2 , a 3 , a 4 , ...
25. Explain how generating functions can be used to find the e) a 1 ,2a 2 ,3a 3 ,4a 4 , ... [Hint: Calculus required here.]
2
number of ways in which postage of r cents can be pasted f) a ,2a 0 a 1 , a + 2a 0 a 2 ,2a 0 a 3 + 2a 1 a 2 ,2a 0 a 4 +
2
1
0
on an envelope using 3-cent, 4-cent, and 20-cent stamps. 2a 1 a 3 + a , ...
2
2
a) Assume that the order the stamps are pasted on does 31. If G(x) is the generating function for the sequence {a k },
not matter. what is the generating function for each of these se-
b) Assume that the stamps are pasted in a row and the quences?
order in which they are pasted on matters.
c) Use your answer to part (a) to determine the number a) 0, 0, 0, a 3 , a 4 , a 5 , ... (assuming that terms follow the
pattern of all but the first three terms)
of ways 46 cents of postage can be pasted on an en-
b) a 0 ,0, a 1 ,0, a 2 ,0, ...
velope using 3-cent, 4-cent, and 20-cent stamps when
c) 0, 0, 0, 0, a 0 , a 1 , a 2 , ... (assuming that terms follow
the order the stamps are pasted on does not matter.
the pattern of all but the first four terms)
(Use of a computer algebra program is advised.)
d) Use your answer to part (b) to determine the num- d) a 0 ,2a 1 ,4a 2 ,8a 3 ,16a 4 , ...
ber of ways 46 cents of postage can be pasted in a e) 0,a 0 , a 1 /2, a 2 /3, a 3 /4, ... [Hint: Calculus required
row on an envelope using 3-cent, 4-cent, and 20-cent here.]
stamps when the order in which the stamps are pasted f) a 0 , a 0 + a 1 , a 0 + a 1 + a 2 , a 0 + a 1 + a 2 + a 3 , ...
on matters. (Use of a computer algebra program is 32. Use generating functions to solve the recurrence relation
advised.) a k = 7a k−1 with the initial condition a 0 = 5.
4
3
2
6
5
26. a) Show that 1/(1 − x − x − x − x − x − x ) is 33. Use generating functions to solve the recurrence relation
the generating function for the number of ways that a k = 3a k−1 + 2 with the initial condition a 0 = 1.
the sum n can be obtained when a die is rolled repeat- 34. Use generating functions to solve the recurrence relation
edly and the order of the rolls matters. a k = 3a k−1 + 4 k−1 with the initial condition a 0 = 1.