CS计算机代考程序代写 discrete mathematics School of Mathematics and Statistics

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.