Due Fri. 1/24:
Read Sect. 1.1.
Do (for class discussion) Ch. 1, ## 1-3.
Due Mon. 1/27:
Read Sect. 1.2.
Do Ch. 1, ## 4, 8, 26.
HAND IN Tues. 1/28: Ch. 1, ## 5, 9, 10.
When solving problems, a systematic solution is better than guesswork. You often may find a solution by intelligent guessing, but then you should look for a way of showing that your solution is correct. This part needs to be systematic if it is to be completely convincing. (This will be clearer after a few days of class!)
Due Wed. 1/29:
Read Sect. 1.3.
Do ## 7, 11, 12, 15, 19.
Due Fri. 1/31:
Read Sect. 1.
Do ## 22-24.
Hand in Mon. 2/3: Ch. 1, ## 13, 16, 25, 27
Read Sects. 3.1-3.3.
Do for discussion on
Tues. 2/4: Ch. 3, ## 1-8, 10, 13.
Wed. 2/5: ## 9, 11, 15.
Hand in Fri. 2/7: Ch. 3, ## 4(c), 5(b), 12, 14.
Read Sects. 3.4-3.5.
Do for discussion on
Tues. 2/11: Ch. 3, ## 16, 17, 19, 21, 23, 25.
Wed. 2/12: ## 24, 30, 32, 37.
Hand in Fri. 2/14: Ch. 3, ## 18, 20, 27, 33, 36, 38.
Allow 15 minutes per problem (minimum) before you give up, even if you feel you're getting nowhere. These problems need time for thought. If you're still stuck, go on to another problem. Return to the sticky problem later (say, the next day). Often, it then looks easier because you tried hard the first time and then gave your mind time to grind it up--I mean, to come up with ideas. To get the advantage of this method, you have to start the problems well ahead of time. Last-minute effort will not work well in this class.
Read Sects. 5.1, 5.2, and 5.3 to (5.10).
Do for discussion on
Tues. 2/25 ## 1-5, 7, 14 in Ch. 5, and A1.
Wed. 2/26 ## 13, 15, and A2. (In #15, "(5.5)" should be "(5.3)".)
Hand in Fri. 2/28 ## 6,8, 9, 11, 12, 16, and A3.
(In #12, assume that k >= 0, but don't assume k <= r.)
A1. Give a combinatorial proof that
A2. Prove combinatorially the formula in Ch. 5, #17:
A3. Give a combinatorial proof of Chapter 5, #11.
Read Sects. 5.3, 5.4, and 5.5. (In Sect. 5.4, stress clutters and Sperner's Theorem 5.4.3.)
Do for discussion on
Tues. 3/4: ## 10, 17, 20, 25, 27, 32, 34, and B1.
Wed. 3/5: ## 15, 21, 23, 28, 31, B2.
Hand in Fri. 3/7 ## 18, 22, 29, and B3.
B1. Prove Ch. 5, #20 combinatorially, assuming r, m, k are integers and r >= m >= k >= 0.
B2. Give a combinatorial proof of formula (5.8). (Hints? The combinatorial proofs of A1 or A2 or Pascal's formula might suggest an idea.)
B3. Give a combinatorial proof of the first equaton in Ch. 5, #7.
Read Section 2.1.
Do (in Ch. 2) for discussion on:
Tues., 3/11: ## 1(for k <= 21 only), 2, 4, 10, 16.
Wed., 3/12: ## 1(for k = 22 and 23), 5, 7, 9, 18.
Fri., 3/14: ## 15, 26, 27, and C1.
Hand in Fri., 3/14 ## 3, 6, 11, 17, 19.
NOTE: Chapter 2 problems require a lot of thought. That means you should start working on the problem ahead of time so you can study it, put it aside if you can't solve it after 15 minutes, and come back to it the next day. (This really does help.) So be sure to start days ahead!
Problem C1. Find a simple formula for the value of the binomial coefficient (-1 binomial n), where n is a nonnegative integer.
Read Section 7.1.
Hand in Fri., 3/21: Ch. 7 ## 1(a), 2, 6.
Read Section 7.2.
Do (in Ch. 7) for discussion on:
Tues., 4/1: ## 1(b), 3(a), 7.9, 10, 12, and D1.
Wed., 4/2: ## 1(c), 3(b,c), 4, 5, 8, 11, 13.
Hand in Fri., 4/4: ## 1(d), 3(d), 14, and D2.
D1. Solve the recurrence h(n) = 3h(n-1) - 2h(n-2) (for n >= 2) with the specified initial conditions.
(a) h(0) = 10, h(1) = 3.
(b) h(0) = 1, h(1) = -1.
D2. Solve the recurrence relation h(n) = h(n-1) + 6h(n-2) (for n >= 2) with h(0) = 4, h(1) = 5.
Read Sections 7.3, 5.6, and 7.4.
Do for discussion on:
Tues., 4/8: Ch, 7 ## 15(a,b), 18, 19, 23(a,c),
and Ch. 5 ## 19, 38, 39.
Wed., 4/9: Ch. 7 ## 15(c), 22, 23(b,d).
Hand in Fri., 4/11: Ch. 7 ## 15(d,e), 16, 20, 23(e), and E1.
E1. (a) Do Ch. 7 # 21 without the 2n term, so it's homogeneous.
(b) Do # 21 as stated in the book.
Read Section 7.5.
Do for discussion on:
Tues., 4/15: ## 24(a,c), 25(a,b,c), 27, 29, 30, 32.
Wed., 4/16: ## 24(b,d), 25(d,f), 26, 28.
(In # 28, "the generating function" should read "a recurrence relation". In this problem, use the method of generating functions to get the recurrence relation, if possible.)
Hand in Fri., 4/18: ## 24(e), 25(g) (the coefficient +16 should be -16), 31, 33.
Due Fri. 4/25:
Read Sections 7.6 and 7.7.
Do for discussion: ## 35, 36, 37(a,b), 38, 41, and F2.
Hand in: ## 37(d), 40, 42, and F1.
Due Mon. 4/28:
Typo in Section 7.6, p. 238:
g(e)(x) = P(n, 0) + P(n, 1)x + ...
= 1 + (n!/1!(n-1)!)x + ...
= (1 + x)n.
(The coefficient of x is missing in the second line.)
F1. (a) What is the sign of (pi binomial n) for each n >= 0?
(b) What is the (ordinary) generating function of the sequence h(n) = (pi binomial n), n >= 0?
(c) What is the exponential generating function of the sequence? As usual, simplify if possible.
F2. (a) Find a simple formula for (½ binomial n) for each n >= 0, and prove it thoroughly. (The proof is given in Sect. 5.6, but it doesn't fill in every detail; I want you to check all the calculations yourself.)
(b) Deduce a "simple" power series expression for sqrt(1 - 4x). (Here you may refer to Section 7.6, but check all the calculations.)
F3. (a) Find a simple formula for (-½ binomial n), for each n >= 0. Give all the details of the derivation.
(b) Deduce a "simple" power series expression for 1/sqrt(1 - 4x).
(c) What is the sequence that has generating function equal to (1 - 4x)-½? Give as simple a formula as you can for the sequence.
Due Fri. 5/2:
Read Section 10.1, pp. 337-347.
Do for discussion: Chapter 10, ## 1, 5, 7, 8, 10, 14-15(i,ii), and G1.
Hand in on Mon. 5/5: ## 3, 8, 11, 12, 14-15(iii), and G2.
Error on page 345: In the table at the top, Cols. A and B should read:
A: 48 48 18 18 6 6 B: 126 30 30 12 12 0
Error on page 347: The top line should read: 16-1 = -14 = 31 in Z45.
G1. Use Ch. 10 # 1 to find
(a) the additive inverse ("negative") of every element of Z4 (mod 4);
(b) the multiplicative inverse ("reciprocal") of every element of Z4 (mod 4, as always) that has a reciprocal.
G2. Use Ch. 10 # 3 to do the same as in G1 for Z5 (mod 5).
Due Mon. 5/5:
Read Section 10.4, pp. 369-383. (Omit the proof of Theorem 10.4.4 and the discussion of finite fields preceding the theorem.)
Do for discussion on:
Tues. 5/6: Ch. 10, ## 37, 38, 42, 44.
Wed. 5/7: # 39, 47.
Hand in Wed. 5/7: Ch. 10, ## 41, 43, 45, 48 (and read 47 to get the definition of "orthogonal mate").
Optional reading: pp. 388 (middle) to 392: some cute questions about Latin squares, not highly technical.
Error (very minor) on page 378: In the bottom line, I think it should say N(1) = infinity.