MATH2069/MATH2969 Discrete Mathematics and Graph 2018

1.   In this question, numerical answers need not be evaluated.

Suppose that there are 77 students enrolled in a course.

(a)  What is the number of ways to select seven representatives to a student forum?

(b)  Each of the students must attend a practice session in one of four dierent locations. What is the number of ways to assign the students to the practice sessions so that each session is attended by at least one student?

(c)  The students were born in 10 dierent countries.   Explain brie  y why at least 8 of them were born in the same country.

(d)  The class received a pack of 100 identical pens from a sponsor. What is the number of ways to distribute the pens among the students so that no one misses out?

2.      (a)  Use characteristic equation to   nd the general solution of the recurrence relation

bn  = 2 bn−2, where n > 2.

(b)  Find the solution of the recurrence relation

an  = 2 an−2 +n (   1)n , where n > 2, satisfying the initial conditions a0  =    2 and a1  = 5.

(c)  Use your solution to part (b) or otherwise to write down a closed formula for the generating function of the sequence an  de  ned by the recurrence relation in part (b).

3.   This question is for MATH2069 students only.

(a)  Prove that for any given formal power series A(z) there exists a unique formal power series B(z) with zero constant term such that B′ (z) = A(z).

(b)  The generating function of a sequence an  is given by the formula

A(z) =        1      

Write down an explicit formula for an .

(c)  Use your solution to part (b) or otherwise to   nd a closed formula for the unique formal power series B(z) provided by the result in part (a).

(d)  Find a closed formula for the unique formal power series C(z) with zero constant term, provided by the result in part (a), such that C′ (z) = B(z).

3.   This question is for MATH2969 students only.

(a)  Let F (z) be a given formal series and let G(z) be the unique formal power series with zero constant term such that G′ (z) = F (z).  Prove that for a given value of a0 , the dierential equation A′ (z) = F (z)A(z) has a unique solution which is given by A(z) = a0 exp  G(z)  .

(b)  Show that the formal power series A(z) = exp   log(1 + z + z2 )  satis  es the

equation A′ (z) = A(z)    1 + 2z   

(c)  Using the results in parts (a) and (b), prove the identity exp   log(1 + z + z2 )  = 1 + z + z2 .

4.      (a)  Explain brie  y why neither of the sequences (1, 1, 1, 1, 5, 5) and (1, 1, 1, 2, 3, 4, 5) is graphic.

(b)  Show that the sequence (1, 1, 2, 2, 3, 3) is graphic by drawing a graph with this degree sequence.

(c)  Show that it is possible to   nd at least two non-isomorphic graphs with the degree sequence (1, 1, 2, 2, 3, 3). Justify your answer.

(d)  What is the total number of isomorphism classes of graphs with the degree sequence (1, 1, 2, 2, 3, 3)? Justify your answer.

5.      (a)  Complete the formulation of the Travelling Salesman Problem:   “Given a connected weighted graph,   nd a walk which . . . ” .

(b)  Find a walk which solves the Travelling Salesman Problem for the following weighted graph. Justify your answer.

b       17          c

f

(c)  Find a minimal spanning tree for this weighted graph.

(d)  Explain brie  y why any connected graph with n vertices and n edges has a cycle.

(e)  Use Cayley’s formula to derive that the number of connected graphs with the vertex set V = {1, 2, . . . , n}, which have n edges, does not exceed 1