Answers to HW #6
1. What are all the partitions of {1,2,3,4}?
A. Organized by the number of cells:
With 1 cell, there's just {{1,2,3,4}}.
With 2 cells, their sizes could be 1+3 or 2+2. There are four of the first type, like {{2},{1,3,4}}, and three of the second, like {{1,3},{2,4}}.
With 3 cells, the only way to break them up is 2+1+1. There are (4 choose 2) of these, like {{2,4},{1},{3}}.
With 4 cells, there's just {{1},{2},{3},{4}}.
In all, 1+4+3+6+1 = 15.
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.
A. If S is a subset of X, define PowerSet(f) (S) = {f(x) : x in S}.
Sometimes this is denoted f(S), by the way.
To show this is injective, let S,T be two subsets of X, and assume PowerSet(f)(S) = PowerSet(f)(T). Then for all s in S, f(s) is in PowerSet(f)(S), so f(s) is in PowerSet(f)(T), so there exists t in T such that f(s) = f(t). But then s = t, since f is assumed 1:1. This shows that S is a subset of T. The same argument works to show T is a subset of S. So they are equal.
b. Also, if f is surjective, show that PowerSet(f) is too.
A. Let T be a subset of Y, and let S = f-1(T). Then I claim that PowerSet(f)(S) = T,as follows. An element y of Y is in PowerSet(f)(S) iff there exists s in S such that f(s) = y. By our definition of S, such a y must be in T. So far this shows that PowerSet(f)(S) is contained in T.
To show the opposite inclusion, we use the fact that f is onto: for any t in T, there does indeed exist s in f-1(T) such that f(s)=t.
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.
A. Given a partition P of Y, there is a natural surjection Y ->> P. Compose the maps X -> Y -> P and define Partitions(f)(P) to be the partition of X induced by the map X -> P.
Given a partition Q of X, we can almost make a partition P of Y; let P = {f(S) : S in Q}.
It is easy to check that the subsets f(S) of Y are disjoint and nonempty; the only worry is that they may not cover Y. But if f is onto, then they do.
It is also easy to check that if we start with a partition of Y, build a partition of X as above, and then build a partition of Y as just described, we get back where we started. That shows that Partitions(f) is injective.
d. Also, if f is injective, show that Partitions(f) is surjective.
A. Let Q be a partition of X, and let P' = {f(S) : S in Q}.
This isn't quite a partition of Y, as explained above; it may not cover Y.
So let P = P' union { Y \ image(f) }, i.e. add an extra cell containing the rest of Y.
Then it is easy to see that Partitions(f)(P) = Q.
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|.
A. The subsets of Y containing X correspond in an obvious way to the subsets of Y \ X,
of which there are 2|Y \ X| = 2|Y| - |X|.
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.)
A. Let C be the coefficient of xm in f(x). Then f(x) - C m! {x choose m} is a polynomial of degree at most m-1. If m=0, we're done; otherwise we use induction on m to say that f(x) - C m! {x choose m} is a linear combination of {x choose k} for k=0,1,...,m-1. Add on C m! {x choose m} to that combination, and we get the desired conclusion.
5a. Say f(x) = sumk=0m ck xk/k!.
Give a formula for the polynomial f'(x).
A. f(x) = sumk=0m-1 ck+1 xk/k!.
This takes a couple of steps; first compute the derivative, then notice that we can drop the k=0 term because it's 0 anyway, then shift k by 1.
b. Say f(x) = sumk=0m ck {x choose k}.
Give a formula for the polynomial f(x+1)-f(x).
A. f(x+1) - f(x) = sumk=0m-1 ck+1 {x choose k}.
This is proved using the Pascal recurrence {x+1 choose k} - {x choose k} = {x choose k-1}. After that do the same as in part (a).
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.)
A. Since the {x choose k} take on only integer values (at x integer), if the (ck) are all integer then f(x) will only take on integer values too. That's the easy direction.
Now assume that f(x) only takes on integer values. Hence f(x+1) - f(x) is also always integer. We calculated it a moment ago:
f(x+1) - f(x) = sumk=0m-1 ck+1 {x choose k}.
This is a polynomial of degree < deg f(x). So by induction, its coefficients are all integers.
So far we know that c1, c2, ..., cm are integers.
But what about c0?
Luckily, c0 = f(0), which was assumed to be an integer. So all the coefficients are integers.
[The point of this question was to give a good way of understanding the surprising fact that a noninteger polynomial may take on only integer values. It says that the usual way of writing polynomials, as combinations of (xk), is not good for studying this question. Rather one should work with combinations of (x choose k)s.]
A. Organized by the number of cells:
With 1 cell, there's just {{1,2,3,4}}.
With 2 cells, their sizes could be 1+3 or 2+2. There are four of the first type, like {{2},{1,3,4}}, and three of the second, like {{1,3},{2,4}}.
With 3 cells, the only way to break them up is 2+1+1. There are (4 choose 2) of these, like {{2,4},{1},{3}}.
With 4 cells, there's just {{1},{2},{3},{4}}.
In all, 1+4+3+6+1 = 15.
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.
A. If S is a subset of X, define PowerSet(f) (S) = {f(x) : x in S}.
Sometimes this is denoted f(S), by the way.
To show this is injective, let S,T be two subsets of X, and assume PowerSet(f)(S) = PowerSet(f)(T). Then for all s in S, f(s) is in PowerSet(f)(S), so f(s) is in PowerSet(f)(T), so there exists t in T such that f(s) = f(t). But then s = t, since f is assumed 1:1. This shows that S is a subset of T. The same argument works to show T is a subset of S. So they are equal.
b. Also, if f is surjective, show that PowerSet(f) is too.
A. Let T be a subset of Y, and let S = f-1(T). Then I claim that PowerSet(f)(S) = T,as follows. An element y of Y is in PowerSet(f)(S) iff there exists s in S such that f(s) = y. By our definition of S, such a y must be in T. So far this shows that PowerSet(f)(S) is contained in T.
To show the opposite inclusion, we use the fact that f is onto: for any t in T, there does indeed exist s in f-1(T) such that f(s)=t.
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.
A. Given a partition P of Y, there is a natural surjection Y ->> P. Compose the maps X -> Y -> P and define Partitions(f)(P) to be the partition of X induced by the map X -> P.
Given a partition Q of X, we can almost make a partition P of Y; let P = {f(S) : S in Q}.
It is easy to check that the subsets f(S) of Y are disjoint and nonempty; the only worry is that they may not cover Y. But if f is onto, then they do.
It is also easy to check that if we start with a partition of Y, build a partition of X as above, and then build a partition of Y as just described, we get back where we started. That shows that Partitions(f) is injective.
d. Also, if f is injective, show that Partitions(f) is surjective.
A. Let Q be a partition of X, and let P' = {f(S) : S in Q}.
This isn't quite a partition of Y, as explained above; it may not cover Y.
So let P = P' union { Y \ image(f) }, i.e. add an extra cell containing the rest of Y.
Then it is easy to see that Partitions(f)(P) = Q.
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|.
A. The subsets of Y containing X correspond in an obvious way to the subsets of Y \ X,
of which there are 2|Y \ X| = 2|Y| - |X|.
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.)
A. Let C be the coefficient of xm in f(x). Then f(x) - C m! {x choose m} is a polynomial of degree at most m-1. If m=0, we're done; otherwise we use induction on m to say that f(x) - C m! {x choose m} is a linear combination of {x choose k} for k=0,1,...,m-1. Add on C m! {x choose m} to that combination, and we get the desired conclusion.
5a. Say f(x) = sumk=0m ck xk/k!.
Give a formula for the polynomial f'(x).
A. f(x) = sumk=0m-1 ck+1 xk/k!.
This takes a couple of steps; first compute the derivative, then notice that we can drop the k=0 term because it's 0 anyway, then shift k by 1.
b. Say f(x) = sumk=0m ck {x choose k}.
Give a formula for the polynomial f(x+1)-f(x).
A. f(x+1) - f(x) = sumk=0m-1 ck+1 {x choose k}.
This is proved using the Pascal recurrence {x+1 choose k} - {x choose k} = {x choose k-1}. After that do the same as in part (a).
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.)
A. Since the {x choose k} take on only integer values (at x integer), if the (ck) are all integer then f(x) will only take on integer values too. That's the easy direction.
Now assume that f(x) only takes on integer values. Hence f(x+1) - f(x) is also always integer. We calculated it a moment ago:
f(x+1) - f(x) = sumk=0m-1 ck+1 {x choose k}.
This is a polynomial of degree < deg f(x). So by induction, its coefficients are all integers.
So far we know that c1, c2, ..., cm are integers.
But what about c0?
Luckily, c0 = f(0), which was assumed to be an integer. So all the coefficients are integers.
[The point of this question was to give a good way of understanding the surprising fact that a noninteger polynomial may take on only integer values. It says that the usual way of writing polynomials, as combinations of (xk), is not good for studying this question. Rather one should work with combinations of (x choose k)s.]
posted by Allen Knutson @ 10:59 AM
0 Comments:
Post a Comment
<< Home