Page 590 - Discrete Mathematics and Its Applications

Supplementary Exercises 569

31. (Requires calculus) This exercise shows how generating are 23 students majoring in AM; 17 in PM; 44 in OR; 63
functions can be used to solve the recurrence relation in CS; 5 in AM and PM; 8 in AM and CS; 4 in AM and
(n + 1)a n+1 = a n + (1/n!) for n ≥ 0 with initial condi- OR; 6 in PM and CS; 5 in PM and OR; 14 in OR and CS;
tion a 0 = 1. 2 in PM, OR, and CS; 2 in AM, OR, and CS; 1 in PM,
a) Let G(x) be the generating function for {a n }. Show AM, and OR; 1 in PM, AM, and CS; and 1 in all four
x

that G (x) = G(x) + e and G(0) = 1. fields.
b) Show from part (a) that (e −x G(x)) = 1, and conclude 36. How many terms are needed when the inclusion–

x
x
that G(x) = xe + e . exclusion principle is used to express the number of ele-
ments in the union of seven sets if no more than five of
c) Use part (b) to find a closed form for a n .
these sets have a common element?
32. Suppose that 14 students receive an A on the first exam
in a discrete mathematics class, and 18 receive an A on 37. How many solutions in positive integers are there
the second exam. If 22 students received an A on either to the equation x 1 + x 2 + x 3 = 20 with 2 <x 1 < 6,
the first exam or the second exam, how many students 6 <x 2 < 10, and 0 <x 3 < 5?
received an A on both exams? 38. How many positive integers less than 1,000,000 are
a) divisible by 2, 3, or 5?
33. There are 323 farms in Monmouth County that have at
b) not divisible by 7, 11, or 13?
least one of horses, cows, and sheep. If 224 have horses,
c) divisible by 3 but not by 7?
85 have cows, 57 have sheep, and 18 farms have all three
types of animals, how many farms have exactly two of 39. How many positive integers less than 200 are
these three types of animals? a) second or higher powers of integers?
b) either primes or second or higher powers of integers?
34. Queries to a database of student records at a college pro-
c) not divisible by the square of an integer greater
duced the following data: There are 2175 students at the
than 1?
college, 1675 of these are not freshmen, 1074 students
d) not divisible by the cube of an integer greater than 1?
have taken a course in calculus, 444 students have taken a
courseindiscretemathematics,607studentsarenotfresh- e) not divisible by three or more primes?
men and have taken calculus, 350 students have taken ∗ 40. How many ways are there to assign six different jobs to
calculus and discrete mathematics, 201 students are not three different employees if the hardest job is assigned
freshmen and have taken discrete mathematics, and 143 to the most experienced employee and the easiest job is
students are not freshmen and have taken both calculus assigned to the least experienced employee?
and discrete mathematics. Can all the responses to the 41. What is the probability that exactly one person is given
queries be correct? back the correct hat by a hatcheck person who gives n
people their hats back at random?
35. Students in the school of mathematics at a university ma-
jor in one or more of the following four areas: applied 42. How many bit strings of length six do not contain four
mathematics (AM), pure mathematics (PM), operations consecutive 1s?
research (OR), and computer science (CS). How many 43. What is the probability that a bit string of length six cho-
students are in this school if (including joint majors) there sen at random contains at least four 1s?
Computer Projects

Write programs with these input and output.

1. Given a positive integer n, list all the moves required in ming to schedule a subset of these talks in a single lecture
the Tower of Hanoi puzzle to move n disks from one peg hall to maximize total attendance.
to another according to the rules of the puzzle.
6. Given matrices A 1 , A 2 ,..., A n , with dimensions m 1 ×
2. Given a positive integer n and an integer k with 1 ≤ k ≤ n, m 2 ,m 2 × m 3 ,...,m n × m n+1 , respectively, each with
list all the moves used by the Frame–Stewart algorithm integer entries, use dynamic programming, as out-
(described in the preamble to Exercise 38 of Section 8.1) lined in Exercise 57 in Section 8.1, to find the mini-
to move n disks from one peg to another using four pegs mum number of multiplications of integers needed to
according to the rules of the puzzle. compute A 1 A 2 ··· A n .
3. Given a positive integer n, list all the bit sequences of 7. Given a recurrence relation a n = c 1 a n−1 + c 2 a n−2 , where
length n that do not have a pair of consecutive 0s. c 1 and c 2 are real numbers, initial conditions a 0 = C 0 and
4. Given an integer n greater than 1, write out all ways to a 1 = C 1 , and a positive integer k, find a k using iteration.
parenthesize the product of n + 1 variables. 8. Given a recurrence relation a n = c 1 a n−1 + c 2 a n−2 and
5. Given a set of n talks, their start and end times, and the initial conditions a 0 = C 0 and a 1 = C 1 , determine the
number of attendees at each talk, use dynamic program- unique solution.