School of Mathematics and Statistics
MAST30012 Discrete Mathematics 2021
Assignment 3
Due 23:59pm Monday 18 October 2021
Student Name Student Number
Tutor’s Name Practice Class Day/Time
Submit your assignment online in Canvas LMS.
Please attach this cover sheet to your assignment or use a blank sheet of
paper as the first page of your assignment with Student Name, Student
Number, Tutors Name, Practice Class Day/Time clearly stated.
• Late submission will not be accepted unless accompanied by a medical certificate
(or a similar special consideration). If there are extenuating circumstances you
need to contact your lecturer, preferably prior to the submission deadline. Medical
certificates are usually required.
• Information on how to submit assignments can be found in the Canvas LMS.
• Full working must be shown in your solutions.
• Marks will be deducted for incomplete working, insufficient justification or incorrect
notation.
• Unless otherwise stated, proofs of identities etc. must use combinatorial arguments.
• There are 3 problems (on three pages) each worth 10 marks.
Q1: The Ammann-Beenker tiling can be specified by the substitution rules:
(a) Further specify the tiling by giving the side lengths and angles of the rhombus
and the factor by which the tiling is expanded in each iteration.
(b) Why does the triangle require an arrow?
(c) Let Rn denote the number of rhombi at step n, and let Tn denote the number
of triangles at step n. Give equations that express (Tn+1, Rn+1) in terms of
(Tn, Rn) and write these equations in matrix form.
(d) Using your results in (c), calculate the total number of tiles after 2 applications
of the substitution rules, starting with a single triangle.
(e) The problem of enumerating the number of rhombi and triangles can be viewed
as counting the number of walks on a weighted directed pseudo-graph G. Draw
this pseudo-graph G.
(f) Use a theorem from lectures to find the generating function S(x) for the total
number of tiles Sn = Tn + Rn after n iterations when we start with a single
triangle.
Q2: You are asked to distribute n apples and n oranges to n children such that each
child receives two pieces of fruit. Let an be the number of ways the fruit can be
distributed.
(a) Prove that
an = [x
n](1 + x+ x2)n.
(b) Using (a), prove that
an =
n∑
k=0
(
n
k
)(
n− k
k
)
=
n∑
k=0
(
n
k
)(
k
n− k
)
,
where we use the fact that
(
a
b
)
= 0 when a < b.
(c) Show that there is a bijection from the set of ways of fruit distribution to the
set of lattice paths from (0, 0) to (n, 0) with step set S = {(1, 1), (1,−1), (1, 0)}.
(d) Show that the generating function G(x) =
∑∞
n=0 anx
n is given by
G(x) =
1
√
1− 2x− 3x2
.
You may wish to consider the problem with no (1, 0) steps first and then make
use of results from Practice Classes and/or Lectures.
Q3: Consider the following permutations:
τ =
(
1 2 3 4 5 6 7 8
3 7 5 8 1 4 2 6
)
σ =
(
1 2 3 4 5 6 7 8
5 7 1 6 3 8 2 4
)
(a) What is the relationship between τ and σ?
(b) Write τ in standard cycle format.
(c) What is the parity of τ?
(d) What is the smallest value of n such that τn is equal to the identity permutation
σI?
(e) Write τ as a product of transpositions.
(f) Represent σ as a bipartite graph.
(g) How is the number of inversions related to this bipartite graph? How many
inversions does σ have?
(h) Write down the set of inversions, Iσ, of σ.