Question 1
Solve the following and explain your answers:
a) How many bit strings of length 9 are there such that every 1 is followed immediately by a 0?
b) How many bit strings of length 10 have at least eight 1s in them.
c) How many onto functions are there from a set with 4 elements to a set with 3 elements?
d) We have 5 Discrete Mathematics textbooks and 7 Signals and Systems textbooks at hand. In how many ways can you make a collection of 4 books from these 12 textbooks with the condition that at least one Discrete Mathematics textbook and at least one Signals and Systems textbook must be in the collection.
Question 2
Let an be the number of subsets of the set f1; 2; 3 ng that do not contain two consecutive numbers.
a) Determine the recurrence relation for an.
b) Solve it by using generating functions.
Question 3
Solve the following recurrence relation with the given initial conditions:
an = 4an 1 + an 2 4an 3
with a0 = 4, a1 = 8, a2 = 34.
Question 4
Let R be a binary relation on real numbers de ned by (x1; y1) R (x2; y2) i 3x1 2y1 = 3x2 2y2. Prove that R is an equivalence relation. Give a graphical representation of [(2; 3)] and [(2; 3)] in the Cartesian coordinate system, where [(x; y)] denotes the equivalence class of (x; y) with respect to R.
1
• Regulations
1. You have to write your answers to the provided sections of the template answer le given.
2. Do not write any extra stu like question de nitions to the answer le. Just give your solution to the question. Otherwise you will get 0 from that question.
3. Late Submission: Not allowed!
4. Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.
5. Newsgroup: You must follow the newsgroup (cow.ceng.metu.edu.tr/c/courses-undergrad/ceng223) for discussions and possible updates on a daily basis.
6. Evaluation: Your latex le will be converted to pdf and evaluated by course assistants. The
.tex le will be checked for plagiarism automatically using "black-box" technique and manually by assistants, so make sure to obey the speci cations.
• Submission
Submission will be done via odtuclass. Download the given template answer le "the4.tex". When you nish your exam upload the .tex le with the same name to odtuclass.
Note: You cannot submit any other les. Don’t forget to make sure your .tex le is successfully compiled in Inek machines using the command below.
$ pdflatex the4.tex
2
