MATH2069/2969 Semester 1 Main, 2019 page 2 of 6

SECTION A: Discrete Mathematics

Use separate writing booklets for sections A and B.

1. A group of 30 people get together to start a small company.

(a) How many different ways can they elect a managing committee of 8 people,

including 2 people appointed as co-presidents?

(b) 100 indistinguishable cards are printed with the company name and logo.

What is the number of ways to distribute the cards among the 30 employees,

given that everyone must have at least 2 cards?

(c) In their new building, there are 10 offices, so exactly 3 people will be assigned

to each office. How many ways are there to assign an office to each employee?

(d) There are 5 priority projects that the company needs to work on. How many

ways are there to assign an employee to each task, so that each task has at

least one person working on it?

2. (a) Write the characteristic polynomial of the recurrence relation

bn = bn−1 + 12 bn−2, where n > 2.

(b) Find the general solution of the recurrence relation

bn = bn−1 + 12 bn−2, where n > 2.

(c) Find one particular solution of the recurrence relation

an = an−1 + 12 an−2 − 4

n, where n > 2.

(d) Find the solution of the recurrence relation

an = an−1 + 12 an−2 − 4

n, where n > 2,

satisfying the initial conditions a0 = 0 and a1 = −2.

turn to page 3

MATH2069/2969 Semester 1 Main, 2019 page 3 of 6

3. This question is for MATH2069 students only.

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

A(z) =

3 + z

(1 + 2z)2

.

Write down an explicit formula for an.

(b) Let bn = a0an + a1an−1 + · · · + ana0. Find a closed form for the generating

function B(z) for the sequence bn.

(c) Let cn = a0 + a1 + · · · + an. Find a closed form for the generating function

C(z) for the sequence cn.

(d) Express the generating function for the sequence 2,−3, 4,−5, 6,−7, . . . in the

form P (z)

Q(z)

, where P (z) and Q(z) are both polynomials.

3. This question is for MATH2969 students only.

(a) Let B(z) =

∑

∞

n=0 bnz

n = log(1 + z) be defined as the unique formal power

series such that B′(z) = 1

1+z

, with b0 = 0. Write down a closed form for bn.

(b) Recall that exp(z) =

∑

∞

n=0

zn

n!

.

Let F (z) be a given formal power 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 differential equation A

′(z) = F (z)A(z) has a unique

solution which is given by A(z) = a0 exp

(

G(z)

)

.

(c) Show that the formal power series A(z) = exp

(

log(1+2z+z2)

)

satisfies the

equation A′(z) = A(z)

2

1 + z

.

(d) Using the previous results, prove the identity

exp

(

log(1 + 2z + z2)

)

= 1 + 2z + z2.

turn to page 4

MATH2069/2969 Semester 1 Main, 2019 page 4 of 6

SECTION B: Graph Theory

Use separate writing booklets for sections A and B.

4. (a) Only one of the sequences (3, 3, 3, 3, 4, 5), (3, 3, 4, 4, 4, 6), and (3, 3, 3, 3, 4, 4)

is graphic. Explain why two of these sequences are not graphic.

(b) Draw a picture of a graph whose degree sequence coincides with the remain-

ing sequence in part (a).

(c) Either write down an Eulerian trail in the following graph, or explain why

none exists. a b

e

g

h

c

d

f

i

j

5. (a) Complete the formulation of the Travelling Salesman Problem: “Given a

connected weighted graph, find a walk which . . . ”.

(b) Find a walk which solves the Travelling Salesman Problem for the following

weighted graph. Justify your answer.

a

b c

e f

d

8

17

17

8 11 4

5

10

6

(c) Find a minimal spanning tree for the weighted graph in (b).

(d) Consider the trees with 7 vertices {1, 2, 3, 4, 5, 6, 7} which have a vertex of

degree 4.

(i) What is the possible number of leaves in such a tree?

(ii) What is the number of isomorphism classes of such trees?

Justify your answer to each of the questions.

(e) A tree has two vertices of degree 4. What is the minimum possible number

of vertices in such a tree? Justify your answer.

turn to page 5

MATH2069/2969 Semester 1 Main, 2019 page 5 of 6

6. This question is for MATH2069 students only.

(a) Let t be a natural number. Define what is meant for a graph G to be t-

colourable.

(b) Use mathematical induction on the number n of vertices in G to show that

any graph G is t-colourable for t = ∆(G) + 1.

(c) The graph H is given by the picture

(i) What is the maximum possible value of the chromatic number χ(H)

as provided by the Brooks Theorem?

(ii) What is the exact value of χ(H)? Justify your answer.

(iii) What are the possible values of the edge chromatic number χ′(H) as

provided by the Vizing Theorem?

(iv) What is the exact value of χ′(H)? Justify your answer.

6. This question is for MATH2969 students only.

(a) For any n > 6 the graph Gn can be drawn as a regular polygon with n

vertices together with all diagonals of the minimal length.

[ For instance, the picture above on this page represents Gn for n = 6 ].

(i) Calculate the chromatic numbers χ(Gn). Justify your answer.

(ii) Calculate the edge chromatic number χ′(G8). Justify your answer.

(iii) Prove that if n is odd then χ′(Gn) = 5.

(b) Find the chromatic polynomial for the graph

turn to page 6

MATH2069/2969 Semester 1 Main, 2019 page 6 of 6

This is the end of the examination paper.