The University of Sydney
School of Mathematics and Statistics
Assignment 2
MATH1064: Discrete Mathematics for Computing Semester 2, 2021
Lecturers: Jonathan Spreer and Behrouz Taji
This individual assignment is due by 11:59pm Thursday 28 October 2021, via
Canvas. Late assignments will receive a penalty of 5% per day until the closing date.
A single PDF copy of your answers must be uploaded in Canvas at https://canvas.
sydney.edu.au/courses/34970/assignments/318114. Please make sure you review
your submission carefully. What you see is exactly how the marker will see your
assignment. Submissions can be overwritten until the due date. To ensure compliance
with our anonymous marking obligations, please do not under any circumstances
include your name in any area of your assignment. The School of Mathematics and
Statistics encourages some collaboration between students when working on problems,
but students must write up and submit their own version of the solutions. If you have
technical difficulties with your submission, see the University of Sydney Canvas Guide,
available from the Help section of Canvas.
This assignment is worth 5% of your final assessment for this course. Your answers should be
well written, neat, thoughtful, mathematically concise, and a pleasure to read. Please cite any
resources used and show all working. Present your arguments clearly using words of explanation
and diagrams where relevant. After all, mathematics is about communicating your ideas. This
is a worthwhile skill which takes time and effort to master. The marker will give you feedback
and allocate an overall letter grade and mark to your assignment using the following criteria:
Mark Grade Criterion
8 A Outstanding and scholarly work, answering all parts correctly, with clear
accurate explanations and all relevant diagrams and working. There are
at most only minor or trivial errors or omissions.
7 B Very good work, making excellent progress, but with one or two substantial
errors, misunderstandings or omissions throughout the assignment.
6 C Good work, making good progress, but making more than two distinct sub-
stantial errors, misunderstandings or omissions throughout the assignment.
5 D A reasonable attempt, but making more than three distinct substantial
errors, misunderstandings or omissions throughout the assignment.
3 C Some attempt, with limited progress made.
1 E Extremely limited attempt.
0 F No credit awarded.
Copyright c© 2021 The University of Sydney 1
1. Let p, q be prime numbers, and let a, b > 0 be integers.
(a) Use the inclusion-exclusion principle to compute the number of integers 0 < c ≤
pa · qb such that gcd(pa · qb, c) > 1.
(b) What is the number of integers 0 < c ≤ pa · qb co-prime to pa · qb?
2. Consider the following identiy: For all a ≥ b ≥ c ≥ 0 we have(
a
b
)(
b
c
)
=
(
a
c
)(
a− c
b− c
)
(a) Show the above identity using an algebraic proof.
(b) Show the above identity using a combinatorial proof.
Hint: Try to count the number of committees with executive subcommittees cho-
sen from a group of people.
3. Suppose that we roll a fair die until a 1 comes up. That is, if in the first roll a 1 comes
up, we stop. Otherwise we keep going. If in the second roll a 1 comes up, we stop.
Otherwise we keep going, etc.
(a) What is the probability of stopping after the n-th roll? That is, what is the
probability that the first 1 comes up on the n-th roll?
(b) What is the expected number of rolls in this experiment?
Hint: You can use this result about the derivative of the geometric series without
proof: For p < 1 we have:
∞∑
i=0
(i + 1)pi =
1
(1− p)2
4. Consider sequences a1a2a3 . . . an, where a1 = 0 and 0 ≤ ai+1 ≤ ai + 1 for 1 ≤ i ≤ n− 1.
For n = 3, we have five such sequences:
000, 001, 010, 011, 012
Let (bn)n∈N be the sequence counting the number of sequences an for fixed n. That is,
b3 = 5.
Show that bn is the n-th Catalan number by constructing a 1-to-1 correspondence between
the above sequences of length n and some other set of objects enumerated by the n-th
Catalan number.
Hint: Consider one of the sets of objects enumerated by the n-th Catalan number from
lectures.
2




















































































学霸联盟

学霸联盟