Student
Number
Semester 2 Assessment, 2019
School of Mathematics and Statistics
MAST30012 Discrete Mathematics
Writing time: 3 hours
Reading time: 15 minutes
This is NOT an open book exam
This paper consists of 6 pages (including this page)
Authorised Materials
• Mobile phones, smart watches and internet or communication devices are forbidden.
• Calculators, tablet devices or computers must not be used.
• No handwritten or print materials may be brought into the exam venue.
• No materials are authorised.
Instructions to Students
• You must NOT remove this question paper at the conclusion of the examination.
• You should attempt all questions. Marks for individual questions are shown.
• Marks are allocated to working, mathematical accuracy and clarity of proofs.
• When appropriate answers may be given in terms of binomial or multinomial coefficients
or other simple expressions.
• If you have any written or printed material related to the subject in your possession, you
should immediately surrender it to an invigilator.
• The total number of marks available is 118.
Instructions to Invigilators
• Students must NOT remove this question paper at the conclusion of the examination.
• Mathematical tables, calculators or any other devices are NOT permitted.
• No written or printed material related to the subject may be brought into the exam.
This paper may be held in the Baillieu Library
MAST30012 Semester 2, 2019
Question 1 (12 marks)
For each part of this question give brief justifications for your answer.
(a) There are 19 distinct doors in a building. How many ways can the doors be opened if:
(i) At least one has to be open.
(ii) Exactly two have to be open.
(iii) At least 3 but no more than 10 doors must be open.
(b) Nine cars are parked in a row, four are red and five are blue. How many ways can the
cars be parked so that no red cars are parked next to each other?
(c) How many distinct words of length eight, using letters taken from the alphabet {a, b, c, d, e}
are there?
Question 2 (12 marks)
(a) Given the three sets A, B and C, state the inclusion/exclusion formula for the size of
A ∪B ∪ C.
(b) Students in a school class all study at least one of the following subjects: mathematics,
physics, and geography. Given that 14 students are studying mathematics, 11 are studying
geography, 11 are studying physics, 6 are studying mathematics and geography, 5 are
studying mathematics and physics, 5 are studying geography and physics, and 3 students
are studying all three subjects:
(i) How many students are there in the class?
(ii) How many studied more than one subject?
(iii) How many studied exactly one subject?
Page 2 of 6 pages
MAST30012 Semester 2, 2019
Question 3 (12 marks)
(a) By using the interpretation of the binomial coefficient as the number of ways of choosing
subsets from a set, show that the number of binomial paths which cross a rectangle from
the point (0, 0) to the point (n,m) is
n+m
n
.
(b) Write down an expression for the number of binomial paths which cross a rectangle from
the point (0, 0) to the point (5n, 4m), with n,m > 1, but which are constrained to have a
vertex on the point (2n,m). Justify your answer.
(c) State the bijection principle.
(d) Give a bijective proof of the formula
n
0
+
n
2
+
n
4
+ · · · =
n
1
+
n
3
+
n
5
+ · · ·
You should argue that your (bijective) function is well defined but you do not need to
prove any other required properties of the function.
Question 4 (10 marks)
(a) State the floor plan lemma. Do not prove the lemma.
(b) Is it possible for a valid floor plan to be such that every room has exactly two doors and
the plan has exactly one outside door? Justify your answer.
(c) Copy the following floor plan into your exam answer booklet and draw the paths which
demonstrate that there must be an even number of rooms with a single door.
Page 3 of 6 pages
MAST30012 Semester 2, 2019
Question 5 (12 marks)
(a) State the binomial coefficient recurrence relation that gives rise to Pascal’s triangle and
thus (or otherwise) give a proof of the binomial theorem
(x+ y)n =
n
k=0
n
k
xkyn−k .
Hint: Try induction.
(b) Prove the identity
n
k=0
(−1)k2n−k
n
k
= 1 .
Hint: Use part (a).
Question 6 (12 marks)
Consider the second order recurrence
an = 7an−1 − 12an−2, n = 2, 3, 4, . . .
with initial conditions a0 = 1, a1 = 2.
(a) Compute the coefficients a2 and a3.
(b) Introduce the generating function
G(x) =
∞
n=0
anx
n,
and show that
G(x) =
P (x)
1− 7x+ 12×2
.
where P (x) is some polynomial.
(c) Write G(x) in partial fraction form and hence find an expression for an.
Page 4 of 6 pages
MAST30012 Semester 2, 2019
Question 7 (12 marks)
(a) Let [4] = {1, 2, 3, 4} and D = {(d1, d2) ∈ [4] × [4] : d1 ≥ d2} be the outcome set with all
the events {(di, dj)} for all (di, dj) ∈ D equally probable.
(i) What is the probability of the event {(2, 1)}?
(ii) What is the probability of getting a pair (d1, d2) such that d1+d2 = 5 ( ie. the event
{(d1, d2) ∈ D : d1 + d2 = 5})?
(b) Consider Dyck paths with 2n steps and complete binary trees with 2n+ 1 nodes.
(i) Draw all possible Dyck paths with six steps.
(ii) Draw all possible complete binary trees with seven nodes.
(iii) Choose two of your Dyck paths from (i) and draw a complete binary tree “on top
of” each path (ie. the nodes of the tree must be the vertices of the path) and thus
illustrate how Dyck paths biject to complete binary trees.
Question 8 (12 marks)
(a) Let σ =
1 2 3 4 5 6
5 2 1 3 4 6
and τ =
1 2 3 4 5 6
2 1 5 6 4 3
be permutations.
(i) Write σ in standard cycle form and as a bipartite graph.
(ii) Compute the composition σ ◦ τ , writing it as a two line array.
(iii) Write down in standard cycle form the inverse permutation σ−1.
(iv) Give the definition of an inversion in a permutation and hence compute the inversion
set of σ.
(v) What is the sign of σ? Justify your answer.
(b) Give a definition of the Stirling numbers of the first kind S1(n, k). From the definition
explain briefly how the recurrence
S1(n, k) = (n− 1)S1(n− 1, k) + S1(n− 1, k − 1).
can be proved using a bijection.
Page 5 of 6 pages
MAST30012 Semester 2, 2019
Question 9 (12 marks)
(a) Let si, i = 1 . . . n−1, be simple transpositions in the set of permutations, Sn of {1, 2 · · · , n}.
(i) Compute the permutation π ∈ S5 in two-line form, given by the composition of
simple transpositions
π = s1s2s1s3s4s2
and also write π as a composition of 3-cycles.
(ii) Write down the three basic algebraic relations that simple transpositions satisfy and
hence show that
s3s1s2s1s4s2 = s3s2s1s4.
(b) In a 15-puzzle, are these board positions related by sliding moves? Justify your answer.
9 10 13 6
7 5 3 8
1 4 11
14 2 12 15
1 12 13 2
8 11 9 10
3 6 7 15
14 5 4
Question 10 (12 marks)
Link diagrams are constructed by taking 2n nodes in a line and joining all the nodes above
the line by ‘arches’ or ‘links’. A link connects exactly two distinct nodes and no two links
intersect. There are five link diagrams on six nodes (n = 3):
The n = 0 case is an empty diagram.
(a) Draw all link diagrams for n ∈ {1, 2}.
(b) Give a schematic diagram (or otherwise) showing how a link diagram with 2n nodes can
be uniquely factorised into two smaller link diagrams.
(c) Use the unique factorisation of link diagrams to give a bijective proof that the number of
link diagrams with 2n nodes satisfies the Catalan recurrence
Cn = C0Cn−1 + C1Cn−2 + C2Cn−3 + · · ·+ Cn−1C0
with C0 = 1. In your proof you do not need to prove your function is a bijection.
End of Exam—Total Available Marks = 118
Page 6 of 6 pages
Library Course Work Collections
Author/s:
Mathematics and Statistics
Title:
Discrete Mathematics, 2019 Semester 2, MAST30012
Date:
2019
Persistent Link:
http://hdl.handle.net/11343/244067