I    Discrete mathematics

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

(a)  What is the number of ways to distribute four yellow cars among six kids?

(b)  What is the number of ways to distribute seven cars of different colours

among three kids so that everyone gets at most three cars?

(c)  What is the number of ways to distribute eight cars of different colours among four kids so that exactly one of them misses out?

(d)  What is the number of ways to distribute six brown and seven green cars among twelve kids so that no one misses out?

2.     (a)  Consider a linear recurrence relation of the form bn  = T1 bn/1  + T2 bn/2  for n > 2, where T1  and T2  are constants with T2   0. Suppose that the roots of its characteristic equation are _2 and λ, where λ is a real number. Find the values of T1  and T2  in terms of λ .

(b)  In each of the cases λ  _2 and λ = _2 write down the general solution of

the relation in part (a).

(c)  Now take λ = _2 and consider the non-homogeneous relation

an  = r1 an/1 + r2 an/2  _ 6 (_2)n  for n > 2.  Explain briefly why a particular solution can be found in the form pn  = A n2 (_2)n  and determine the value of the constant A.

(d)  Write down a closed formula for the generating function of the sequence pn .

3.     (a)  Show that the formal power series

o    3n zn

n!

(b)  Show that the equation A\ (z) _ 3A(z) = 0 for an arbitrary formal power

series

A(z) =       an zn

n=0

is equivalent to the recurrence relation (n + 1)an+1 _ 3an  = 0 with n > 0 for the sequence an .

(c)  Assuming that a value of a0 is given, solve the recurrence relation in part (b) and use your solution to prove that any formal power series A(z) satisfying the equation A\ (z) = 3A(z) is proportional to E(z).

(d)  Set B(z) = E(z2 _ 4z). Find a polynomial p(z) in z such that B(z) satisfies the equation B\ (z) = p(z)B(z).

II    Graph theory

4.     (a)  Consider the three sequences:

a = (1, 1, 2, 3, 3, 3, 4, 4, 4, 6),

b = (0, 0, 1, 1, 1, 2, 4, 4, 4, 6),

c = (0, 1, 1, 2, 2, 3, 4, 4, 4, 5).

(i)  Exactly one of the sequences above is graphic.  Determine which se- quence is graphic and explain why the other two sequences are not graphic.

(ii)  Construct a graph that has a degree sequence equal to the sequence

from part (i).

(b)      (i)  Compute the Pr¨ufer sequence for the tree

Explain your answer.

(ii)  Construct the labelled tree that has Pr¨ufer sequence (1, 1, 2, 2, 4, 4, 4).

(c)  How many labelled trees are there with 10 vertices and 5 leaves?

5.  The questions below all concern the following weighted graph:

Throughout this  question,  whenever you need to  order the vertices  always  order them alphabetically when you have a choice!  For example, of some parts you may want to order the vertices of the same degree alphabetically.

(a)  Use Dijkstra’s algorithm to compute the minimal distances d(C, v), for v e

{A, B, C, D, E, F, G, H}. What is the shortest path from C to H? Show all of your working.

(b)  Use Prim’s algorithm to find a minimal spanning tree in this graph, starting

from vertex E . What is the weight of the minimal spanning tree? Show all of your working.

(c)  Considering the graph as an unweighted graph, use a Breadth-first search to find a spanning tree for this graph starting from the vertex C .  Show all of your working.

(d)  Use the Welsh-Powell algorithm to find a colouring of the graph using the ordered set of colours blue, green, red and yellow. Is this a minimal colouring?

6.  The questions below all concern the following graph H:

(a)  Does H have an Eulerian circuit? Justify your answer.