Take Home Exam 4

Description

Question 1

Solve the following and explain your answers:

1. How many bit strings of length 9 are there such that every 1 is followed immediately by a 0?

2. How many bit strings of length 10 have at least eight 1s in them.

3. How many onto functions are there from a set with 4 elements to a set with 3 elements?

4. 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 a_n be the number of subsets of the set f1; 2; 3 ng that do not contain two consecutive numbers.

1. Determine the recurrence relation for a_n.

2. Solve it by using generating functions.

Question 3

Solve the following recurrence relation with the given initial conditions:

a_n = 4a_{n 1} + a_{n 2} 4a_{n 3}

with a₀ = 4, a₁ = 8, a₂ = 34.

Question 4

Let R be a binary relation on real numbers de ned by (x₁; y₁) R (x₂; y₂) i 3x₁ 2y₁ = 3x₂ 2y₂. 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.

• 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