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]

- Phone+44 7868 815209
- Emailadmin@solvemyproject.com
- Open Hours24x7

- Phone+44 7868 815209
- Emailadmin@solvemyproject.com
- Open Hours24x7