Description

CENG223
Discrete Computational Structures
Homework 4

Question 1
Assume that a small universe has 10 distinct stars and 100 distinct planets so that 20 of them are habitable and 80 of them are nonhabitable by humans. How many ways are there to form a galaxy with exactly one star, 2 habitable planets and 8 nonhabitable planets such that there is at least six nonhabitable planets between the two habitable ones?
Note: For this question, a galaxy is a bound system with a star at the center and a group of planets that orbit the star. Different orders of the planets create different galaxies.
Question 2
Find all solutions of the recurrence relation an = 2an−1 + 15an−2− 36an−3 + 2n.
Hint: Find both the homogeneous and particular solutions. You can leave the homogeneous solution with unknown coefficients.
Question 3
A computer generates activation codes of any length such that codes have odd number of odd digits where each digit is in the range of [0,9]. Let an be the number of valid n-digit activation codes. Find the recurrence relation for an .
Question 4
Use generating functions to solve the recurrence relation ak = 3ak−1−3ak−2+ak−3 with initial conditions a0 = 1, a1 = 3 and a2 = 6.
Note: You can use the useful generating functions table in the textbook (just refer which of them you are using clearly).
1
Question 5
Let R be the relation on the set of ordered pairs of positive integers such that ((a,b),(c,d)) ∈ R if and only if a + d = b + c.
(a) Show that R is a equivalence relation.
(b) What is the equivalence class of (1,2) with respect to R.
1 Regulations
1. You have to write your answers to the provided sections of the template answer file given. Other than that, you cannot change the provided template answer file. If a latex structure you want to use cannot be compiled with the included packages in the template file, that means you should not use it.
2. Do not write any other stuff, e.g. question definitions, to answers’ sections. Only write your answers. Otherwise, you will get 0 from that question.
3. Late Submission: Not allowed
5. Newsgroup: You must follow the odtuclass discussions (https://odtuclass.metu.edu.tr) for discussions and possible updates on a daily basis.
2 Submission
Submission will be done via odtuclass. Download the given template file, ”hw4.tex”, when you finish your exam upload the .tex file with the same name to odtuclass.
Note: You cannot submit any other files. Don’t forget to make sure your .tex file is successfully compiled in Inek machines using the command below.
$ pdflatex hw4.tex
2