#2, MATH3825/MATH3855/COMP3805, Winter 2017 Due on 24 March. Total: 100 marks 1. [10 marks] You are building a wall out of Lego bricks. You have bricks of length 1 and bricks of length 2. Let bn be the number of different ways in which you can build a wall of length n. It is easy to see that b1 = 1 and b2 = 2. (a) [4 marks] Find a recurrence relation for the sequence {bn }. (b) [6 marks] Solve the above recurrence relation. 2. [10 marks] Given a sequence {qn } with q0 = 0. Assume that {qn } satisfies a non-homogeneous recurrence relation as follows: qn+1 2qn = 3n (n 0). (a) [4 marks] Find the generating function Q(x) for {qn }. (b) [6 marks] Show that qn = (3n 2n ). 3. [18 marks] (a) [6 marks] Show that x(1 + x)/(1 x)3 is the generating function for the sequence whose nth term is n2 . (b) [6 marks] Let A(x) be the generating function for the sequence {an } and define sn = a0 + a1 + an (n 0). Show that the generating function for the sequence {sn } is S(x) = A(x) . 1x (c) P [6 marks] Use the results of (a) and (b) to find a formula for n 2 i=0 i . 4. [10 Marks] (Required for MATH3855, Bonus for other students) 1 (a) [5 marks] Let A(x) be the generating function for the sequence {an } and define sn = nan Show that the generating function for the sequence {sn } is S(x) = x dA . dx (b) [5 marks]P Use (a) and the method from Question 3 to find a formula for ni=0 i3 . 5. [10 marks] Use the generating function method to find the number of ways to write 12 = (S1 ) + (S2 ) + (S3 ) + (S4 ) + (S5 ) such that 0 Si 4 for each i. 6. [10 marks] Show that the number of partitions of a positive integer n where all parts appear less than 4 times equals the number of partitions of n where no part is divisible by 4. 7. [8 marks] (a) [2 marks] Find a necessary and sufficient condition on n such that the complete graph Kn contains an Eulerian walk which is not closed? (b) [2 marks] Find a necessary and sufficient condition on n such that the complete graph Kn contains a closed Eulerian walk? (c) [2 marks] Find a necessary and sufficient condition on m, n such that the complete bipartite graph Km,n contains an Eulerian walk which is not closed? (d) [2 marks] Find a necessary and sufficient condition on m, n such that the complete bipartite graph Km,n contains a closed Eulerian walk? 8. [15 marks] Consider the graph G. 2 c d b a f g e (a) [3 marks] Does G have a Hamiltonian cycle? If yes, give an example; otherwise, explain why G doesn't have a Hamiltonian cycle. (b) [3 marks] Does G have a closed Eulerian walk? If yes, explain the reason and give an example; otherwise, explain why G doesn't have a closed Eulerian walk. (c) [3 marks] Does G have an Eulerian walk which is not closed? If yes, explain the reason and give an example; otherwise, explain why G doesn't have an Eulerian walk which is not closed. (d) [3 marks] What is the chromatic number of G? Give a vertex colouring of G and explain why fewer colours is not possible. (e) [3 marks] Is G planar? If yes, show Euler's formula about the number of vertices, edges, and regions in G. If not, briefly explain why G is nonplanar. 9. [9 marks] Let T = (V, E) be a tree with V = {v1 , . . . , vn } with n 2 and let di be the degree of vertex vi . Show that T has at least two vertices with degree 1. Using the above result and induction, prove that n X di = 2n 2. i=1 3