Page 591 - Discrete Mathematics and Its Applications

570 8 / Advanced Counting Techniques

9. Given a recurrence relation of the form f (n) = 11. Given a positive integer n, produce the formula for the
af (n/b) + c, where a is a real number, b is a positive number of elements in the union of n sets.
integer, and c is a real number, and a positive integer k,
k
find f(b ) using iteration. 12. Given positive integers m and n, find the number of onto
functions from a set with m elements to a set with n ele-
10. Given the number of elements in the intersection of three ments.
sets, the number of elements in each pairwise intersection
of these sets, and the number of elements in each set, find 13. Given a positive integer n, list all the derangements of the
the number of elements in their union. set {1, 2, 3,...,n}.

Computations and Explorations

Use a computational program or programs you have written to do these exercises.

1. Find the exact value of f 100 , f 500 , and f 1000 , where f n is 7. Compute the number of operations required to multi-
the nth Fibonacci number. ply two integers with n bits for various integers n in-
cluding 16, 64, 256, and 1024 using the fast multiplica-
2. Find the smallest Fibonacci number greater than
tion described in Example 4 of Section 8.3 and the stan-
1,000,000, greater than 1,000,000,000, and greater than
dard algorithm for multiplying integers (Algorithm 3 in
1,000,000,000,000.
Section 4.2).
3. Find as many prime Fibonacci numbers as you can. It is 8. Compute the number of operations required to multiply
unknown whether there are infinitely many of these.
two n × n matrices for various integers n including 4, 16,
4. Write out all the moves required to solve the Tower of 64, and 128 using the fast matrix multiplication described
Hanoi puzzle with 10 disks. in Example 5 of Section 8.3 and the standard algorithm
5. Write out all the moves required to use the Frame–Stewart for multiplying matrices (Algorithm 1 in Section 3.3).
algorithm to move 20 disks from one peg to another peg 9. Find the number of primes not exceeding 10,000 using
using four pegs according to the rules of the Reve’s puz- the method described in Section 8.6 to find the number of
zle. primes not exceeding 100.
6. Verify the Frame conjecture for solving the Reve’s puzzle 10. List all the derangements of {1, 2, 3, 4, 5, 6, 7, 8}.
for n disks for as many integers n as possible by show- 11. Compute the probability that a permutation of n objects
ing that the puzzle cannot be solved using fewer moves is a derangement for all positive integers not exceeding
than are made by the Frame–Stewart algorithm with the 20 and determine how quickly these probabilities ap-
optimal choice of k. proach the number 1/e.

Writing Projects

Respond to these with essays using outside sources.

1. Find the original source where Fibonacci presented his 4. Discuss as many different problems as possible where the
puzzle about modeling rabbit populations. Discuss this Catalan numbers arise.
problem and other problems posed by Fibonacci and give
some information about Fibonacci himself. 5. Discuss some of the problems in which Richard Bellman
first used dynamic programming.
2. Explain how the Fibonacci numbers arise in a variety of 6. Describe the role dynamic programming algorithms play
applications, such as in phyllotaxis, the study of arrange- in bioinformatics including for DNA sequence compari-
ment of leaves in plants, in the study of reflections by son, gene comparison, and RNA structure prediction.
mirrors, and so on.
7. Describe the use of dynamic programming in economics
3. Describe different variations of the Tower of Hanoi puz- including its use to study optimal consumption and sav-
zle, including those with more than three pegs (includ- ing.
ing the Reve’s puzzle discussed in the text and exer-
cises), those where disk moves are restricted, and those 8. Explain how dynamic programming can be used to solve
where disks may have the same size. Include what is the egg-dropping puzzle which determines from which
known about the number of moves required to solve floors of a multistory building it is safe to drop eggs from
each variation. without breaking.