University of Aberdeen Department of Mathematics Author Irakli Patchkoria Date 17.02.2023 Code MA1510 Combinatorics Assignment 1 >Deadline for submission is 23pm Friday February 24, 2023. Please submit it on My Aberdeen. 20 Points in total. Justify your answers and SHOW ALL WORKING. Poor presentation may result in the loss of marks. Let A be a set with 9 elements. How many odd size subsets does A have [3 marks]1. Use induction to prove that 17n 17 is divisible by 4 for all n ∈ N. [5 marks]2. Define f, g : N→ R by f(n) = n4 + 2 and g(n) = 3n3 · cos(n4 + 1).3. a) Prove that g(n) = O(f(n)). [2 marks] b) Prove that f(n) 6= O(g(n)). [3 marks] 4. a) Compute the binomial coefficient ( 9 5 ) . Justify and explain your answer. [1 mark] b) Let n ≥ 2. Show that the number of 2-subsets of an n-element set is equal to n(n 1) 2 . [1 mark] c) Suppose you have two boxes. The first box has 9 distinguishable fruits and the second has 7 distinguishable sandwiches. Suppose you want to take 6 fruits and 3 sandwiches from these boxes for a hike. How many choices do you have You can leave the answer in terms of binomial coefficients. [5 marks]
