School of Mathematics and Statistics
MAST30012 Discrete Mathematics
Answers to the 2019 Exam
Q1: (a) (i) 219
(ii)
(
19
2
)
(iii)
∑10
k=3
(
19
k
)
(b)
(
6
2
)
= 15
(c) 58
Q2: (a) |A ∪B ∪ C| = |A|+ |B|+ |C| − |A ∩B| − |A ∩ C| − |B ∩ C|+ |A ∩B ∩ C|
(b) |M | = 14, |G| = 11, |P | = 11, |M ∩ G| = 6, |M ∩ P | = 5, |G ∩ P | = 5,
|M ∩G ∩ P | = 3
(i) |M ∪G ∪ P | = 14 + 11 + 11− 6− 5− 5 + 3 = 23
(ii) |(M ∩P )∪ (M ∩G)∪ (P ∩G)| = |M ∩P |+ |M ∩G|+ |P ∩G| − |M ∩P ∩
G| − |M ∩ P ∩G| − |M ∩ P ∩G|+ |M ∩ P ∩G| = 6 + 5 + 5− 2 · 3 = 10
(iii) 13
Q3: (a) Each path bijects to a binary word in {E,N}∗ of length n+m. Complete the
proof by yourself.
(b)
(
2n+m
2n
)(
3n+3m
3m
)
(c) See the lecture notes.
(d) Note that you are required to give a bijective proof. Complete the proof by
yourself.
Q4: (a) See the lecture notes.
(b) No.
(c) Complete by yourself.
Q5: (a) Recurrence relation:
(
n
k
)
=
(
n−1
k
)
+
(
n−1
k−1
)
. Using this and induction on n, prove
the binomial theorem by yourself.
(b) Set x = −1, y = 2 in (a) and evaluate LHS and RHS.
Q6: (a) a2 = 2, a3 = −10
(b) Use the given recurrence relation and initial conditions to work out a functional
equation for G(x). Solve this equation to obtain the required expression of
G(x). You will see that P (x) is a linear function of x. Complete the proof by
yourself.
(c) an = 2 · 3n − 4n
Q7: (a) (i) 1
10
(ii) 1
5
(b) Draw all these by yourself.
Q8: (a) (i) (1 5 4 3)
(ii)
[
1 2 3 4 5 6
2 5 4 6 3 1
]
(iii) σ−1 = (1 3 4 5)
(iv) See the lecture notes for the definition of an inversion.
Iσ = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 3)}
(v) sign(σ) = (−1)|Iσ | = (−1)5 = −1
(b) See the lecture notes for the definition of S1(n, k). Note that you are required
to give a bijective proof of the identity. For this purpose, you need to define two
sets whose cardinalities are given by LHS and RHS, respectively, and establish
a bijection between them. Complete the proof by yourself.
Q9: (a) (i) (1 3 2)(2 4 5)
(ii) See the lecture notes for these basic algebraic relations.
s3s1s2s1s4s2 = s3s2s1s2s4s2 = s3s2s1s4s2s2 = s3s2s1s4
(b) The two board positions can be related by sliding moves as their corresponding
permutations have the same parity (odd).
Q10: (a) Draw these link diagrams by yourself.
(b) Consider the last node and the link connected to it. Complete the proof by
yourself.
(c) Complete the proof by yourself.