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 parts 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 parts 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.