Discrete Computational Structures
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.
