1.  Note: the answers to this question should not be evaluated numerically. They should be left in terms of factorials and/or binomial coefficients.

(a) You roll a fair 8-sided die, with faces numbered from 1 to 8, 40 times. Find the

probability of getting a multiple of 3 exactly 5 times.

(b)  Find in how many ways you can distribute 6 red pens, 3 blue pens, and 10 black

pens to 19 people, so that each one gets one pen.

(c)  State the Inclusion-Exclusion Principle for finite sets A1 , . . . , An  (with n < 2). Use it to deduce the generalised sum rule.

(d)  Find in how many ways you can distribute 8 different gifts to 3 people so that everyone gets at least two gifts.

2.   (a)  Find the solution of the difference equation

yn+2 _ 4yn+1 + 3yn  = 2 . 3n

with initial conditions y0  = 2, y1  = 5.

(b) Consider the following difference equation of Riccati type

yn+1yn  _ yn+1 + 3yn  = _1 .

(i)  Find the general solution.

(ii)  Find the solution with initial condition y0  = _3.

(c)  Suppose you want to type sequences of vowels (that is, the letters a , e , i , o and u).  However, the e key on your keyboard is defective and every time you press it, it outputs ee instead of just e .

Let yn  the number of sequences of length n you can type in this way.

(i)  Find y0 , y1 , y2 .

(ii) Write a second-order difference equation for the value of yn . (iii)  Solve the difference equation.

3.   (a)   (i)  State the Handshaking Lemma.

(ii)  In each of the following cases, either draw a picture of the graph which

matches the information, or explain why no such graph exists. ·  G1  with 4 vertices, each of degree 2;

·  G2  with 5 vertices, each of degree 3;

·  G3  with 6 vertices, of which 2 of degree 1, 4 of degree 2;

·  G4  with 5 vertices, of which 1 of degree 1, 2 of degree 2, 2 of degree

4.

(b)  Let G = (V, E) be the graph with n vertices and m edges.

(i)  Define the incidence matrix B = (b﹔ ,j )1>﹔ >n,1>j >巾  of G .        (ii)  Define the oriented incidence matrix C = (c﹔ ,j )1>﹔ >n,1>j >巾 .  (iii)  Recalling that the (i,j)-entry of the matrix CCT  is given by

(  c﹔ ,仅 cj,仅 ,

1>仅>巾

explain what the entries of CCT  correspond to in the graph G .

(iv) Calculate the number of spanning trees of the graph with the following

(c)  Determine whether the graphs G1 , G2  with the following adjacency matrices are isomorphic:

4.   (a)  Use the connectedness algorithm to determine the number of connected com- ponents of the graph with the following adjacency matrix.