University of Aberdeen
Department of Mathematics
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. 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]