\ MA/CSC 416, Nathan Reading, Homework assignments

Homework assignments

You can expect each assignment to be posted to this page at least a week before it is due. Please contact me immediately if you have any trouble getting the assignment.

Sections and problem numbers refer to your assigned text. Recall that there are hints and answers to selected problems in the back of your text.

Problems marked with an asterisk are more advanced problems. (For example, in Assignment 2, problems 10b and 10c are advanced.) Many of you will be able to do these, and I would encourage all of you to try them. But don't panic if you try hard on them and can't get them. It would be better to spend more time on the other problems rather than spending a lot of time on asterisked problems.

Homework is due by 4:15 pm (under the door in my office), or you can feel free to turn it in earlier in the day, in class.

Assignment 1, due Monday, January 13

Part of the assignment is to carefully read the relevant sections of the text!
Section 1.1
5, 6, 7d, 7f, 8, 15a, 15c, 15f, 16, 17, 18, 21.
Please don't bother learning the details of the "POSTNET" system. Just read the "POSTNET" example as an illustration of the ideas of the chapter.
For Problems 5, 6, and 7: No "prose" is necessary, but do 6 "by hand."
About Problem 8: These can be proven by mathematical induction. Part a can also be proved in a "cooler" way that you may be familiar with. Is there a clever way to do part b without induction? In any case, you must write at least one of these proofs as a formal induction. Also, in part c, what is the integer?

I think it's fair to warn you that Assignment 1 is easier than what you should usually expect, since we haven't learned much yet. Assignment 2 is a better example of a typical assignment.

Assignment 2, due Monday, January 27

Part of the assignment is to carefully read the relevant sections of the text, except that on 1.3, you only need to read up to Example 1.3.7.
Section 1.2
9b, 10a, 10b^*, 10c^*, 17, 18, 26, 28.
For 10a, 10b and 10c, you must give a combinatorial proof. Think about what each side of the formula counts. I'll get you started: The left side of 10a counts how many ways you can choose a k-element subset S of [n] and then choose an r-element subset T of S. Problem 10c is significantly harder than 10a and 10b.
For 28, you actually need another assumption for this to be correct: assume all the a_i's are greater than zero. Also, to make clear exactly what Problem 28 is asking: if we were factoring 6, we would count "2 times 3" and "3 times 2" as the same factorization.
Section 1.3
15, 17, 18.

Assignment 3, due Monday, February 3

Part of the assignment is to carefully read the relevant sections of the text.
Section 1.2
Do Problem 12 twice: once combinatorially and once using Pascal's identity.
This will be graded as two separate problems. How do you prove combinatorially that a number is even? (If you have a room full of people, how can you tell, without counting if there is an even number of people? What if it was a ballroom full of people?)
Section 1.5
1, 6, 7, 8a, 8b, 15.
For 1, please find a very brief way to do each part. For 8a, instead of doing this "using Equations (1.9)-(1.10) and (1.12)," use Problem 7 and do this the way we did the other cases in class. For 15, give a combinatorial proof.

Assignment 4, due Monday, February 10

Part of the assignment is to carefully read the relevant sections of the text. I know I say that every week. Are you doing it? Maybe it would save you time!
Section 1.6
4, 7, 14, 17, 19, 27, 29.
For 7, give a bijective proof. For 19 and 29, here is one way you might approach it: Let a_n be the quantity that you are trying to show is equal to F_n. (Or, choose your favorite letter instead of a.) Then show that a_n satisfies the defining recursion of the Fibonacci numbers, given in the first sentence of problem 15 (including the base case). Why is that enough? The book's hints suggest different approaches to 19 and 29, and you're welcome to use those, as long as you explain them completely. For 27, the answers are in the back, so you will get no credit unless you make it clear that you know where the answers come from.
Section 1.7
6, 7, 8.

Assignment 4.5, "due" Monday, February 17

Since there is no homework to turn in on February 17, your assignment is to:

Spend time looking at the posted solutions to Assignments 1, 2, 3, and 4. The idea is to "close the cycle" of learning about homework problems you already did, and to learn more about what is expected on homework. (The "sample solutions" are showing you the length and level of detail that is appropriate for your answers.)

Get ahead on Assignment 5. We have covered all the relevant material in class.

Assignment 5, due Monday, February 24

Part of the assignment is to carefully read the relevant sections of the text. In Section 1.9, you can safely skip everything from Definition 1.9.6 on (except maybe glance at Theorem 1.9.9). If you have time, the rest of the section is interesting but not required.
Section 1.7
11, 12, 19.
For Problem 11a, reason using the formula for the multinomial coefficient. For Problem 11b, you must argue using the multinomial theorem and part a. You may not look up some number-theory proof. Instead, think about what happens if you set x₁=x₂=...=x_k=1 in the multinomial theorem. Problem 12 is asking you to flesh out the inductive proof mentioned in the book just before the formal proof of the Binomial Theorem (Theorem 1.7.1). For Problem 19, think about what happens if you expand out the given product. It may help you to write this using "..." notation instead of a Product symbol (Pi) and Summation symbol (Sigma).
Section 1.8
2, 6, 9^*, 13ab, 14abc, 18.
The asterisked problem (#9) is an extra challenge for those of you who want it. Focus your attention on the other problems first. For Problem 18: Do the n=0 and n=1 cases by writing Ferrers diagrams of all 5 partitions of 4 and all 30 partitions of 9. Do the n=2 case by continuing the table in Figure 1.8.2 all the way down to n=14.
Section 1.9
3de.
This problem gets super easy if you understand what we covered in class. (It's also in the book.) If you're doing it by a long calculation, stop. Find the easy way.

Assignment 6, due Monday, March 3...

...is not really due because you have a midterm that day.

Since we haven't had time to go through a homework-solutions cycle for Section 2.1, I am recommending some basic problems for you to look at before the midterm.
(Please don't turn these in.)
Section 2.1
1, 2, 3, 4, 5, 7.

To prepare for the test, I would suggest the following (probably in this order of importance):
Look over the homework solutions and make sure you understand all the homework problems.
Look over class notes and make sure you understand what we did in class.
Read over the book sections that we covered. (Through Section 2.1, except that 1.3 was only covered up to Example 1.3.7, Section 1.4 was skipped, in Section 1.9, we skipped Definition 1.9.6 and everything after that, and Section 1.10 was skipped.)

Assignment 7, due Monday, March 17

This assignment is due the Monday after Spring Break. If that seems cruel, consider: If you work on this before Spring Break, you have a whole non-Spring-Break week to do it, just like a usual homework assignment. I strongly encourage you to do that, and get some rest over Spring Break.

Part of the assignment is to carefully read the relevant sections of the text.
Section 2.1
6abc, 8, 13, 17, 17alt, 20ab.
"Problem 17alt" is a modification of Problem 17: For any integer m greater than or equal to 2, and any integer n in [m]:
(a) How many partitions of [m] with n blocks have 1 and 2 in the same block? Your answer should be phrased in terms of Sterling numbers of the second kind.
(b) How many partitions of [m] with n blocks have 1 and 2 in different blocks? Your answer should be phrased in terms of Sterling numbers of the second kind. Do not use part a to answer this question, i.e. don't write "S(m,n) - (answer to a)" for your answer.
(c) Since the answers to (a) and (b) must add up to S(m,n), you have proved an identity for Sterling numbers of the second kind. Write down and simplify this identity. Does it look familiar?
Section 2.2
10, 14, 15, 18, 19, 24, 25.
All of these problems in Section 2.2 get fairly easy once you look at them in the right way. So the task is to look at them in the right way. You might want to ask questions, for example in office hours.

Assignment 8, due Monday, March 24

Part of the assignment is to carefully read the relevant sections of the text. For this assignment, you can safely stop reading Section 2.3 after Example 2.3.8.
Section 2.2
29, 31.
Section 2.3
4, 5, 12, 18.
Do Problem 12 combinatorially, not by the formula for derangements.
Additional Problem:
The right hand side of the inclusion-exclusion formula I gave in class is quite different from the right hand side of the inclusion exclusion formula given in the book. Explain briefly why these are two different ways of writing the same thing.

Assignment 9, due Monday, March 31

Part of the assignment is to carefully read the relevant sections of the text. You will need to pick up the definition of "cycle type" from the reading. You do not need to read Section 3.1.

This assignment has a lot of problems, but many (not all) of them are simply asking you to understand the objects that we are talking about. If you are keeping up on your reading and on lectures, and if you start this in time to ask questions, this will not be a hard assignment.

Section 2.3
13a, 13b, "13d".
Do Problem 13a combinatorially, not by the formula for derangements. (There is a hint in the back of the book.) For Problem 13b, use 13a. Problem "13d" is one I made up:
13d. Use Problem 13b to give an inductive proof of equation (2.18), which we also proved in class.
Section 2.4
3bdf, 4fh, 8, 9, 13, 14, 19a, 19b^*.
As you'll know from your reading, the book's "sequence notation" is what I called "one-line notation" in class.
For Problem 9, please "compute," don't just "list-and-count."
If you find yourself working really hard on #19a, step back and think about what it is really asking.
The asterisked problem (#19b) is an extra challenge for those of you who want it. Focus your attention on the other problems first. It may be quite hard, depending on your experience. I would suggest an "overcount" method if you try 19b. (Indeed, the answer itself suggests the overcount method, since it is a fraction...)
Section 2.5
3, 4, 11a(twice!).
Problem 11a should have a familiar "feel." You must do it two different ways: Combinatorially, and using the generating function "g_m(x)" for Stirling numbers of the first kind. (Possibly, the combinatorial proof may be so easy that you didn't feel like you did anything!)
Section 3.1
4.

Assignment 10, due Monday, April 7

Part of the assignment is to carefully read the relevant sections of the text. You can safely stop reading Section 2.5 after Corollary 2.5.5.
Section 2.5
11b, 14, 15^*.
The asterisked problem (#15) is a really hard extra challenge for those of you who want it. Focus your attention on the other problems first. The book gives a hint using generating functions. I'm curious about a combinatorial proof. This looks like it should have one, but I don't see it.

Non-book problem:
Prove these three facts about elementary symmetric functions for any a₁, a₂, ... , a_n, and any nonnegative integer r.
(a): E_r(0,a₁,a₂,...,a_n)=E_r(a₁,a₂,...,a_n).
(b): E_r(-a₁,-a₂,...,-a_n)=(-1)^rE_r(a₁,a₂,...,a_n).
(c): E_n+1(a₁,a₂,...,a_n)=0.

Section 4.2
2a, 2b, 2c, 2d, 2e, 2f, 2g, 3a, 4a.
Here are some general hints for Problem 2. (I'm not saying which parts they apply to.) Is this a problem we have done before? Can you factor out a power of x? Can you break the power series into a sum of two power series? What about integrating or differentiating? By the way, each part of problem 2 will be worth 2 points, rather than the traditional 4, just to keep problem 2 for overwhelming the grading scale.

Assignment 11, due Monday, April 14

Part of the assignment is to carefully read the relevant sections of the text.
Section 4.2
6a, 6cde, 10, 15, 17.
Does anyone see how to do Problem 6b (not assigned)? I don't.

For 10, let me try to clarify the phrasing: a_n is the number of compositions of n with exactly k parts with none of the parts larger than m. Also, this generating function works quite differently from the partition generating function, so comparisons to P(x) might lead you in the wrong direction. Instead, think about this: Suppose I had to make a k-part composition with parts of size at most m and suppose I DON'T decide ahead of time what the parts add up to. What sequence of k decisions would I make?

For number 15, the book gives a hint which may seem cryptic. Ignore the hint, and do the problem by thinking. In the problem, b_n is the coefficient of xⁿ in (1-x)g(x). Find a formula for b_n. Naturally, the answer will involve the a's.

Section 4.3
16, 17, 20^*, 32.
For 16, they mean "find a product formula for..."
For both 16 and 17, I would recommend that you look back at notes and/or the book and try to understand what we did for generating functions for partitions with distinct parts and partitions with odd parts. If you understand these, you can modify them to answer 16 and 17.

Problem 20 is optional. For 20b, do not do this by computing partial derivatives the way the book suggests. (This is a red herring...even Merris told me he doesn't remember how to compute the partial derivatives tidily.) Instead, write a formula relating the quantity P(x,t)-P(x,xt) to the quantity P(x,t). Compare coefficients in the formula to obtain a recursive formula for f_n(x). Then solve the recursion for f_n(x). (By the way, there is a combinatorial approach that is even easier.)

For 32, look for a generating function proof. (Hint: What is this saying for k=2?)

Assignment 12, not due

Part of the assignment is to carefully read the relevant sections of the text.
In Section 5.1, you can focus your attention on graphs rather than the pigeonhole principle. You can stop reading Section 5.2 after the proof of Theorem 5.2.5. You are not responsible for Section 5.3 on the final, but if you want to reinforce what we covered in class, read through Definition 5.3.9.

This would have been due April 21, but since that is the last day of our class and since our final is so early, you don't have to turn this one in. Important: You are responsible, on the exam, for all the material from the course, including material covered on this homework. But to help you focus your preparation, I have marked in bold the problems that you should focus on to prepare for the final. (In case it's hard to tell what is bold, the problems are 5.1: 13,14,15 and 5.2: 2abc,3a,11,12,19.)

Section 5.1
4, 6, 7, 8, 13, 14, 15.
For 8, try subdividing the triangle into smaller triangles in a natural way.

Section 5.2
2a, 2b, 2c, 3a, 3b, 11, 12, 19.
Problem 3 will test your understanding of the proof I will give in class of Ramsey's Theorem.

Section 5.3
1a, 1b, 1c, 3, 9c, 9d, 13, 21
For Problem 9, a graph is bipartite, by definition, if and only if it has a 2-coloring. Problem 21 gets at your basic understanding of what is going on. The book gives a hint for Problem 21: factor the polynomial. I'll even save you some time and give you the factorization. f(x)=x(x-1)^2(x-3)^2(x-4). So what?