Problem 2 Problem 3 Problem 3 Which of the following is the cardinality of the set of all surjections from a set A, where |A| = n, and B, where |B| = m.

(a) m^{n}

(b) \frac{m!}{(m−n)!}

(c) \binom{n}{m}m^{n−m}m!

(d) None of the above. Solution (d) None of the above. Problem 5 Problem 5 Suppose you have a collection of 41 balls, of which you know that 39 have normal weight and one is abnormal — either heavy or light, but you don’t know which. Is there a way to determine which ball is abnormal with 4 weighings? If so, demonstrate the approach, otherwise prove that it is impossible. Solution Problem 6

(a) Solve the following homogeneous recurrence, assuming that T (0) = 1 and T (1) = 1.

T (n) = T (n − 1) − \frac{1}{4}T (n − 2)

Solution (b) Find a closed-form solution for the infinite sum:

∑_{n=0}^{∞} T (n)

Solution