Page 587 - Discrete Mathematics and Its Applications

566 8 / Advanced Counting Techniques

the formula for the number of elements in the union of three the number of onto functions from a set with m elements
finite sets: to a set with n elements:

|A ∪ B ∪ C|=|A|+|B|+|C|−|A ∩ B|−|A ∩ C|
m
m
−|B ∩ C|+|A ∩ B ∩ C| n − C(n, 1)(n − 1) + C(n, 2)(n − 2) m
− ··· + (−1) n−1 C(n, n − 1) · 1 m
the principle of inclusion–exclusion:

|A 1 ∪ A 2 ∪ ··· ∪ A n |= |A i |− |A i ∩ A j |
the number of derangements of n objects:
1≤i≤n 1≤i<j≤n

+ |A i ∩ A j ∩ A k |

1≤i<j<k≤n 1 1 n 1
D n = n! 1 − + − ··· + (−1)
n+1 1! 2! n!
−··· + (−1) |A 1 ∩ A 2 ∩ ··· ∩ A n |

Review Questions

1. a) What is a recurrence relation? 9. a) Derive a divide-and-conquer recurrence relation for
b) Find a recurrence relation for the amount of money the number of comparisons used to find a number in
that will be in an account after n years if $1,000,000 a list using a binary search.
is deposited in an account yielding 9% annually. b) Give a big-O estimate for the number of comparisons
2. Explain how the Fibonacci numbers are used to solve Fi- used by a binary search from the divide-and-conquer
bonacci’s problem about rabbits. recurrence relation you gave in (a) using Theorem 1
in Section 8.3.
3. a) Find a recurrence relation for the number of steps
needed to solve the Tower of Hanoi puzzle. 10. a) Give a formula for the number of elements in the union
b) Show how this recurrence relation can be solved using of three sets.
iteration. b) Explain why this formula is valid.
4. a) Explain how to find a recurrence relation for the num- c) Explain how to use the formula from (a) to find the
ber of bit strings of length n not containing two con- number of integers not exceeding 1000 that are divis-
secutive 1s. ible by 6, 10, or 15.
b) Describe another counting problem that has a solution
d) Explain how to use the formula from (a) to find the
satisfying the same recurrence relation.
number of solutions in nonnegative integers to the
5. a) Whatisdynamicprogrammingandhowarerecurrence equation x 1 + x 2 + x 3 + x 4 = 22 with x 1 < 8, x 2 <
relations used in algorithms that follow this paradigm? 6, and x 3 < 5.
b) Explain how dynamic programming can be used to 11. a) Give a formula for the number of elements in the union
schedule talks in a lecture hall from a set of possible of four sets and explain why it is valid.
talks to maximize overall attendance.
b) Suppose the sets A 1 , A 2 , A 3 , and A 4 each contain 25
6. Define a linear homogeneous recurrence relation of de-
elements, the intersection of any two of these sets con-
gree k.
tains 5 elements, the intersection of any three of these
7. a) Explain how to solve linear homogeneous recurrence sets contains 2 elements, and 1 element is in all four
relations of degree 2. of the sets. How many elements are in the union of the
four sets?
b) Solve the recurrence relation a n = 13a n−1 − 22a n−2
for n ≥ 2if a 0 = 3 and a 1 = 15. 12. a) State the principle of inclusion–exclusion.
c) Solve the recurrence relation a n = 14a n−1 − 49a n−2
b) Outline a proof of this principle.
for n ≥ 2if a 0 = 3 and a 1 = 35.
k
8. a) Explain how to find f(b ) where k is a positive inte- 13. Explain how the principle of inclusion–exclusion can be
ger if f (n) satisfies the divide-and-conquer recurrence used to count the number of onto functions from a set
relation f (n) = af (n/b) + g(n) whenever b divides with m elements to a set with n elements.
the positive integer n. 14. a) How can you count the number of ways to assign m
b) Find f(256) if f (n) = 3f (n/4) + 5n/4 and jobs to n employees so that each employee is assigned
f(1) = 7. at least one job?