Last HW due Friday June 6

1. What are all the partitions of {1,2,3,4}?

2. Let PowerSet(X) denote the set of subsets of X, and Partitions(X) denote the set of partitions of X. Let f:X->Y be a function from X to Y.

a. Define a function (properly called PowerSet(f)) from PowerSet(X)->PowerSet(Y), in a nontrivial way. Once you've found the right one, you should be able to prove that if f is injective, then PowerSet(f) is too; do prove this.

b. Also, if f is surjective, show that PowerSet(f) is too.

c. Define a function (properly called Partitions(f)) from Partitions(Y)->Partitions(X) -- it goes backwards! Once you've found the right one, you should be able to prove that if f is surjective, then Partitions(f) is injective; do prove this.

d. Also, if f is injective, show that Partitions(f) is surjective.

3. Let X be a subset of Y, where Y is finite. How many subsets of Y contain X? Give (and explain) a formula in terms of |X|, |Y|.

4. Let f(x) be a polynomial of degree m. Show that f can be written as a linear combination of the polynomials {x choose k} for k=0,1,...,m. (I shouldn't need to say it, but hint: induction.)

5a. Say f(x) = sum_k=0^m c_k x^k/k!.
Give a formula for the polynomial f'(x).

b. Say f(x) = sum_k=0^m c_k {x choose k}.
Give a formula for the polynomial f(x+1)-f(x).

c. Use (b) to prove that a polynomial f(x) takes on integer values for every integer x if and only if it is an integer combination of {x choose k}s.
(So we come full circle: one of the first things we proved was that {x choose 2} is such a polynomial.)