MATH1004A Semester 2 2018
The University of Sydney
School of Mathematics and Statistics
MATH1004
Discrete Mathematics
November 2018 Lecturer: Oded Yacobi
Time Allowed: Writing - one and a half hours; Reading - 10 minutes
Exam Conditions: This is a closed-book examination — no material permitted. Writing
is not permitted at all during reading time.
Family Name: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . SID: . . . . . . . . . . . . . . . . . . . . . . . . . . .
Other Names: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Seat Number: . . . . . . . . . . . . . . . . .
Please check that your examination paper is complete (0 pages) and indicate by signing below.
I have checked the examination paper and affirm it is complete.
Signature: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Date: . . . . . . . . . . . . . . . . . . . . . . . . .
Page 1 of 0
MATH1004A Semester 2 2018 Page 2 of 0
This examination has three printed components: the Question Paper (this
booklet),
a Graph Sheet (yellow) and a Multiple Choice Answer Sheet (white).
THESE MUST NOT BE REMOVED FROM
THE EXAMINATION ROOM.
The examination has two sections: Multiple Choice and Extended
Answer.
The Multiple Choice Section is worth 50% of the total examination;
there are 15 questions; The questions are of equal value.
All questions may be attempted.
Answers to the Multiple Choice questions must be coded onto
the Multiple Choice Answer Sheet.
The Extended Answer Section is worth 50% of the total examination;
there are 0 questions; all questions may be attempted;
questions are of equal value;
working must be shown;
Question 3(ii)(a) must be answered on the Graph Sheet.
University-approved calculators may be used.
Marker’s use
only
MATH1004A Semester 2 2018 Page 3 of 0
There are three questions in this section, some with a number of parts. Write your
answers in the space provided below each part. You must show your working and give
reasons for your answers. If you need more space there are extra pages at the end of the
examination paper.
1. (a) Consider the sets A = {a, b, c, 1, 2, 3}, B = {b, c, 1, 4, 5}, and C = {1, 2, 3, 4, 5}.
Write down explicitly a bijection from A \B to B ∩C, or explain why one does not
exist.
(b) Let X, Y be sets and consider functions f : X → Y and g : Y → X. Suppose that
for every y ∈ Y we have that f(g(y)) = y. Prove that f is surjective.
(c) Suppose that A,B, C are sets. Prove the statement
A \ (B ∩ C) = (A \B) ∪ (A \ C).
(A Venn diagram alone is not sufficient, be explicit about the elements in A, B, and
C.)
2. (a) How many arrangements are there of the letters of WOOLLOOMOOLOO? (In all
parts of this question it is not necessary to evaluate formulas involving factorials,
binomial coefficients, etc.)
(b) How many arrangements are there with the three Ls together?
(c) How many arrangements are there with the W and M together?
3. Consider the sequence (an)n≥0 defined by the recurrence
an+2 = an+1 + 12an
with initial conditions a0 = 0 and a1 = 1. Let
F (z) =
∞∑
n=0
anz
n = a0 + a1z + a2z
2 + · · ·
be the generating function for this sequence.
(a) Compute the terms a2 and a3.
(b) Write down and solve the characteristic equation of the recurrence.
(c) Using part (b), or otherwise, find a closed formula for an.
(d) Explain why
F (z)− zF (z)− 12z2F (z) = z
and deduce that
F (z) =
z
1− z − 12z2 .
(e) Use the method of partial fractions applied to part (d) and geometric series to
recover the same closed formula that you found in part (c).
MATH1004A Semester 2 2018 Page 4 of 0
(f) Consider a new sequence (bn)n≥0 that corresponds to a generating function G(z)
with the following rational form:
G(z) =
1
(1− z − 12z2)2 .
Prove that for n ≥ 0,
bn =
n∑
k=0
ak+1an+1−k.

欢迎咨询51作业君