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作业君