MATH1004 Semester 2, 2019
The University of Sydney
School of Mathematics and Statistics
MATH1004
Discrete Mathematics
November 2019 Lecturer: Emily Cliff
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 (3 pages) and indicate by signing below.
I have checked the examination paper and affirm it is complete.
Signature: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Date: . . . . . . . . . . . . . . . . . . . . . . . . .
This examination consists of 3 pages, numbered from 1 to 3.
There are 3 questions, numbered from 1 to 3.
University-approved calculators may be used.
Marker’s use
only
Page 1 of 3
MATH1004 Semester 2, 2019 Page 2 of 3
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) Let A be the set {1, 2, a, b, c, d} and let B be the set {2, a, c, d}. Define a function
f : P(A)→ P(B) by f(S) = S ∩B. Is f injective? Prove or disprove.
(b) With A,B, f as in the previous part of the question, is f surjective? Prove or
disprove.
(c) Let A be a finite set and suppose that f : A → A is surjective. Prove that f is
injective.
(d) Suppose that Z is a set with subsets X, Y ⊂ Z. Prove or disprove the following
statement:
Z \ (Y \X) = (Z \ Y ) ∪X
(A Venn diagram alone is not sufficient; be explicit about elements in X, Y , and
Z.)
2. (a) Assiniboia is a town is Saskatchewan, Canada. How many arrangements are there
of the letters of ASSINIBOIA? (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 no consecutive Is?
(c) How many arrangements are there with at least one set of all like letters together
(i.e. at least one instance of III, AA, or SS)?
3. Consider the sequence (an)n≥0 defined by the recurrence
an+2 = −6an+1 − 5an
with initial conditions a0 = −4 and a1 = 0. 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) + 6zF (z) + 5z2F (z) = −4− 24z
and deduce that
F (z) =
−4− 24z
1 + 6z + 5z2
.
MATH1004 Semester 2, 2019 Page 3 of 3
(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).
(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 + 6z + 5z2)
.
Prove that for n ≥ 0,
bn = −1
4
n∑
k=0
(−6)kan−k.
End of Examination