1.  (a) Let A be the set {1, 2, a, b, c, d} and let B be the set {2, a, c, d}.  Define a function f : p(A) → p(B) by f(S) = S n B . Is f injective? Prove or disprove.

(b) With A, B, f  as in the previous part of the question, is f  surjective?   Prove or disprove.

(c) Let A be a finite set and suppose that f  : A → A is surjective.  Prove that f is injective.

(d) Suppose that Z is a set with subsets X , Y c Z .  Prove or disprove the following statement:

Z \ (Y \ X) = (Z \ Y) u X

(A Venn diagram alone is not sufficient; be explicit about elements in X , Y , and Z .)

2.  (a) Assiniboia is a town is Saskatchewan, Canada.  How many arrangements are there of the letters of ASSINIBOIA? (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 no consecutive Is?

(c) How many arrangements are there with at least one set of all like letters together (i.e. at least one instance of III, AA, or SS)?

3. Consider the sequence (an )n≥＋  defined by the recurrence ano2  = _6ano1 _ 5an

with initial conditions a＋  = _4 and a1  = 0. Let

o

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

n3＋

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) + 6zF (z) + 5z2 F (z) = _4 _ 24z

and deduce that

_4 _ 24z  

F (z) =

(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≥＋  that corresponds to a generating function G(z)

with the following rational form:

G(z) =

Prove that for n > 0,