MATH 211 Final, Fall 2001
American University of Beirut · Discrete Structures · 2 pages
More MATH 211 files
Show the text of this final exam
IERICAN UNIVERSITA
LIBRARY
OF BRETRED
FINAL EXAM.; MATH 211
FALL 2002; FEB. 5; 11:30 A.M.-1:30 P.M.
Instructions:
e Let N, P and Z be the sets natural numbers, positive integers and
integers respectively.
e The examination consists of five independent questions each of which
consists of three or four partial questions.
e The grade allocated to each question appears next to the question.
e The total grade is 100.
AMERICAN UNIVERSITY
LIBRARY
OF REIRET
4. (a) Give an explicit formula for s,
if sy
= 2,8, = 1, and 8n = Sn, +28, _9
for n > 2.
(6 points)
(b) Let 5 = {a,b} and Sny
n & N, be the number of words of length n
not containing the string aa. Find a recurrence formula for s,. (6 points)
(c) Give an explicit formula for $n ifs, = 1/6 and su, = 28, + n3 for
n & P; and show that s, = O(n’). Hint: som
= 2M [51 + 1/2 OG! f (24/24).
(6 points)
5. (a)
A group of 60 persons were surveyed. Twenty-six like pizza, thirty-two
like hamburgers, thirty like shawarma, fourteen like both pizza and hamburg-
ers, seven like both pizza and shawarma, ten like hamburgers and shawarma,
and two like all three. How many dislike all three’
(6 points)
(b) A class of 20
0 students votes on a date for an exam. Each votes for
Just one of the five working days of the week. How many different ways may
they vote?
(6 points)
(c)
Nine students enter one elevator in the basement of College Hall. Each
exits at Hoor 1, 2, 3,
4 or 5. How many different ways can this happen?
(6 points)
(d) A class of 2¢
) students is divided into 4 mutually disjoint study groups
of equal size 5 students. How Inany different ways can this happen?
Once Again,