1.  (a) Consider the sets A =  {a, b, c, 1, 2, 3}, B  =  {b, c, 1, 4, 5}, and C  =  {1, 2, 3, 4, 5}. Write down explicitly a bijection from A / B to B n C, or explain why one does not exist.

(b) Let X, Y be sets and consider functions f : X → Y and g : Y → X .  Suppose that for every y e Y we have that f(g(y)) = y . Prove that f is surjective.

(c) Suppose that A,B, C are sets. Prove the statement    A / (B n C) = (A / B) n (A / C).

(A Venn diagram alone is not sufficient, be explicit about the elements in A, B, and C .)

2.  (a) How many arrangements are there of the letters of WOOLLOOMOOLOO? (In all parts of this question it is not necessary to evaluate formulas involving factorials, binomial coefficients, etc.)

(b) How many arrangements are there with the three Ls together?

(c) How many arrangements are there with the W and M together?

3. Consider the sequence (an )n>0  defined by the recurrence an+2  = an+1 + 12an

with initial conditions a0  = 0 and a1  = 1. Let

o

F (z) =       an zn  = a0 + a1 z + a2 z2 + . . .

n=0

be the generating function for this sequence.

(a) Compute the terms a2  and a3 .

(b) Write down and solve the characteristic equation of the recurrence.

(c) Using part (b), or otherwise, find a closed formula for an .

(d) Explain why

F (z) _ zF (z) _ 12z2 F (z) = z

and deduce that

1 _ z _ 12z2 .

(e) Use the method of partial fractions applied to part  (d) and geometric series to recover the same closed formula that you found in part (c).

(f) Consider a new sequence (bn )n>0  that corresponds to a generating function G(z)

with the following rational form:

G(z) =

Prove that for n > 0,