Lecturer: Trevor Welsh Second Semester, 2021
School of Mathematics and Statistics University of Melbourne
MAST90030: Advanced Discrete Mathematics
Assignment 3
Due: 11.55pm on Monday, October 11
This assignment is worth 9% of your final MAST90030 mark. Marks will be awarded for clear explanations.
Question 1. (40 marks)
Use a sign-reversing involution to prove that
∑
k>0
(−1)n−k
(
n − k
k
)
=


1 if n ≡ 0 (mod 3) ,
0 if n ≡ 2 (mod 3) ,
−1 if n ≡ 1 (mod 3) ,
for all n ∈ N0. Hint: use the fact that
(
n−k
k
)
is the number of Fibonacci pavings of an n-board using exactly k
dimers.
Question 2. (40 marks)
(a) Conjecture an identity for which one side is:
n∑
k=0
(−1)k
(
n
k
)2
.
(The other side should not contain a summation.) (10 marks)
(b) Use a sign-reversing involution to prove the identity you conjectured in part (a) for all n ∈ N0. (30 marks)
Question 3. (20 marks)
For n > 3, letA =
(
(0, 0), (1, 0), . . . , (n − 1, 0)
)
andB =
(
(n,n), (n,n − 1), . . . , (n, 1)
)
.
(a) By drawing paths, conjecture the cardinality of the set L¯[A → B] of non-intersecting n-tuples of binomial
paths that have startpoints inA and endpoints inB. (10 marks)
(b) Write down the matrix whose elements are all non-zero binomial coefficients, and whose determinant is equal
to
L¯[A → B] . (10 marks)

欢迎咨询51作业君