Student
Number
Semester 2 Assessment, 2018
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 5 pages (including this page)
Authorised Materials
• Mobile phones, smart watches and internet or communication devices are forbidden.
• No materials are authorised.
• No written or printed materials may be brought into the examination.
• No calculators of any kind may be brought into the examination.
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 120.
Instructions to Invigilators
• Students must NOT remove this question paper at the conclusion of the examination.
• Initially, students are to receive a 14 page script booklet.
• No special materials are to be supplied.
This paper may be held in the Baillieu Library
Blank page (ignored in page numbering)
MAST30012 Semester 2, 2018
Question 1 (14 marks)
(a) Consider three pairs of shoes, the first pair are blue, the second pair red and the third
pair green. How many ways can the shoes be arranged on a shoe rack (ie. in a line) such
the blue pair are always next to each other? Left and right shoes are considered different.
(b) Consider a group of 23 people from which two equal sized teams and one referee are to
be chosen. Give two clearly different methods to calculate how many possible ways this
can be done.
(c) How many ways can the letters of the word “ADIABAT” be rearranged so that no two
‘A’s are adjacent.
(d) Let [6] = {1, 2, 3, 4, 5, 6} and D = {(d1, d2) ∈ [6]× [6] : d1 ≤ d2} be the outcome set with
all the events Ti,j = {(di, dj)} for all (di, dj) ∈ D equally probable.
(i) What is the probability of the event {(1, 1)}?
(ii) What is the probability of getting a pair (d1, d2) such that d1 +d2 = 7 ( ie. the event
{(d1, d2) ∈ D : d1 + d2 = 7})?
Question 2 (14 marks)
(a) Give a count-two-ways proof of the identity:
k
(
n
k
)
= n
(
n− 1
k − 1
)
.
(b) Give a bijective proof of the following identities:
i)
n∑
k=0
(
n
k
)
= 2n ii)
n∑
k=0
k
(
n
k
)
= n2n−1 .
In your bijective proofs you need only define the two sets and the bijection between them
– there is no need to prove your map is a bijection.
The two sets must be clearly different sets.
(c) Give a brief combinatorial (ie. not algebraic) argument that explains the identity
n−1∑
k=0
(2k + 1) = n2 ,
that is, that the sum of the first n positive odd integers is a square.
Page 2 of 5 pages
MAST30012 Semester 2, 2018
Question 3 (8 marks)
(a) A bag contains a certain number of multicoloured marbles. Each marble contains up to
three of the colours: red, green and blue. It is known that 14 marbles contain red, 11
marbles contain blue, 11 marbles contain green, 6 marbles contain red and blue, 5 marbles
contain red and green, 5 marbles contain blue and green, and 3 contain all three colours.
Using inclusion-exclusion determine how many marbles are in the bag.
(b) Using inclusion-exclusion and subtraction theorems, find how many ways three different
coloured balls (one red, one green and one blue) can be placed into three coloured boxes
(one red, one green and one blue) such that:
(i) each box contains exactly one ball, and
(ii) none of the boxes contain a ball of the same colour.
Verify your answer by listing all configurations.
Question 4 (10 marks)
(a) Define the Stirling number of the first kind, S1(n, k) and give a combinatorial interpreta-
tion in terms of people seated at tables.
(b) Use the table seating interpretation to argue that S1(n, k) satisfies the partial difference
equation
S1(n, k) = (n− 1)S1(n− 1, k) + S1(n− 1, k − 1) ,
with S1(n, 0) = 0, S1(n, n) = 1.
(c) Compute all the Stirling numbers S1(3, k), either by using the partial difference equation
or by finding all the corresponding permutations.
Question 5 (12 marks)
(a) Define the Ramsey number R(a, b) using the coloured complete graph interpretation.
(b) State and prove the theorem for R(n, 2).
(c) Consider a regular hexagon (6 sided polygon) with all sides having length two. If seven
points are placed at random inside the polygon prove (or disprove) that at least two points
must be a distance no more than two apart.
(d) Consider an interval with the two endpoints labelled 0 and 1 respectively. Suppose that the
interval is broken up into subintervals , with each endpoint labelled by 0 or 1 at random.
Show that the number of subintervals labelled (0, 1) minus the number of subintervals
labelled (1, 0) is equal to 1.
Page 3 of 5 pages
MAST30012 Semester 2, 2018
Question 6 (12 marks)
(a) Let the sequence (an)n≥0 satisfy the recurrence relation
12an+2 = 7an+1 − an , a0 = a1 = 2 .
(i) Show that the generating function G(x) =
∑∞
n=0 anx
n is a rational function (ie. a
ratio of polynomials).
(ii) Using a partial fraction expansion find an exact expression for an.
(b) Assuming the sequence (bn)n≥0 has generating function
H(x) =
1 + x
x2 − 3x+ 2
find the recurrence relation satisfied by bn.
Question 7 (12 marks)
(a) Draw all the monomer-dimer pavings of a 4-board.
(b) Prove that the number of monomer-dimer pavings of an n-board, Pn satisfies the recur-
rence relation
Pn+2 = Pn+1 + Pn
with P1 = 1, P2 = 2. If you use a bijective map you only need show it is well defined.
(c) Find the generating function, P (x) =
∑∞
n=1 Pnx
n, where Pn is the number of monomer-
dimer pavings of an n-board.
(d) Using the generating function obtained in part (c) express Pn as a sum of binomial coef-
ficients. Hint: it is simpler to start with 1 + P (x).
Question 8 (16 marks)
(a) Consider the two permutations σ = 23145 and τ = 24531.
(i) Write σ as a two-line array and in standard cycle form.
(ii) Write σ−1 in standard cycle form.
(iii) Write σ ◦ τ as a two-line array.
(iv) Find the set of inversions of τ .
(v) Calculate sgn(τ).
(vi) Write σ as a composition of simple transpositions
(b) Let α and β be permutations of {1, 2, . . . , n}. Prove that
sgn(α ◦ β) = sgn(α) sgn(β) .
You may use any theorems from lectures.
Page 4 of 5 pages
MAST30012 Semester 2, 2018
Question 9 (12 marks)
(a) Using the snake-pattern labelling of the squares of the 7-puzzle (the blank cell is grey),
compute the permutation, in cycle notation, corresponding to the move µ2 given by
What is the parity of µ2?
(b) Consider the product of simple transpositions s5s4s3s5s2. Determine where each of the
numbers 1, 2, 3, 4, 5, 6 are mapped to and write the permutation as a two-line array.
(c) Write down the three algebraic relations that simple transpositions satisfy and use these
to find the set of reduced word decompositions of
σ = s4s2s3s2s1.
Question 10 (10 marks)
(a) Draw the five Dyck paths with six steps. For each path find the complete binary tree the
path bijects to. Draw at least one intermediate diagram showing how you found each tree.
The bijection must depend on the path structure alone and not arise simply by listing the
complete binary trees.
(b) Take 2n nodes in a line and join them above the line by ‘arches’. An arch connects exactly
two distinct nodes and no two arches intersect. There are five arch diagrams on six nodes:
Find a bijection from the five arches on six nodes to the set of six step Dyck paths. Give
a brief explanation of your map (it is not necessary to prove it is a bijection).
End of Exam—Total Available Marks = 120
Page 5 of 5 pages
Library Course Work Collections
Author/s:
Mathematics and Statistics
Title:
Discrete Mathematics, 2018, Semester 2, MAST30012
Date:
2018
Persistent Link:
http://hdl.handle.net/11343/220969