Math 386: Combinatorics Homework Assignments
Fall 2009
Go to rules for homework | announcements | course information | syllabus.
HOMEWORK I (8/31)
Due on Tues., 9/1:
Read Ch. 1 intro, Sect. 1.1, beginning of Sect. 1.2.
Do (for class discussion) Ch. 1, ## 1, 2, 3, 5, 10.
Due on Wed., 9/2:
Read Sect. 1.2.
Do (for discussion) Ch. 1, ## 2(again), 12, 14, 16, 17.
Due on Fri., 9/4:
Read Sect. 1.4, 1.6.
Do (for discussion) Ch. 1, ## 15, 22, 24, 38, and A1, A2.
Hand in Tues., 9/8:
Ch. 1, ## 4(a), 7, 21.
Problem Set A
- A1. How many Latin squares of order 2 are there?
- A2. What is the difference between a magic square and a Latin square? Better question: How many differences can you list?
- A3. Following the procedure in Problem 1.16 in the book, do you still get a magic square if you allow the original square to have any n2 distinct integers?
HOMEWORK II (8/31)
Due on Tues. 9/8:
Read Sect. 2.1-2.
Do (for discussion) Ch. 2, ## 2, 4(a).
Due on Wed. 9/9:
Do (for discussion) Ch. 2, ## 1, 3, 4(b), 6, 7.
Due on Fri. 9/11:
Do (for discussion) Ch. 2, # 8.
Hand in Fri., 9/11:
Ch. 1, ## 8, 9.
Ch. 2, ## 4(c), 5(a), 9.
Extra! Extra! Much more about magic squares in only 5 pages.
HOMEWORK III (9/13)
Read Sects. 2.3-5.
Do for discussion on
Tues. 9/15: Ch. 2, ## 8, 9, 11, 13.
Wed. 9/16: Ch. 2, ## 16, 17, 19(a), 22.
Hand in Fri. 9/18: Ch. 2, ## 5(b), 15, 19(b), 28.
(Due before 2:00 p.m. in my mailbox at the Math Dep't or at my office. I gladly accept early homework. No late homeworks.)
HOMEWORK IV (9/18)
Read for Mon.-Tues., 9/21-22: Sects. 2.6, 4.2.
Read for Wed., 9/21-22: Sect. 5.1.
Do for discussion on
Tues., 9/22: Ch. 2, ## 31, 34, 41, 60; Ch. 4, # 6(a), 7(a).
Wed., 9/23: Ch. 2, ## 39, 48, 63; Ch. 4, ## 5, 8(b); Ch. 5, # 2.
Fri., 9/25: Ch. 2, # 50; Ch. 5, ## 1, 3.
Hand in Thursday, 9/24 by 4:00 p.m.: Ch. 2, ## 40, 51, 64(a); Ch. 4, ## 6(b), 7(b), 8(c), 9.
TEST I is on Tuesday, Sept. 29!
HOMEWORK V (9/29)
Read for Fri., 10/2: Sects. 5.1-2.
Do for discussion on
Fri., 10/2: Ch. 5, ## 2, 3, 4-6, 7-8, 15, and especially B2.
Mon., 10/5: Ch. 5, ## 9, 16, 23, and especially B3.
Tues., 10/6: Ch. 5, ## 18, 24, B1. (Keep a copy of your proof when you submit this.)
Hand in Wed., 10/7: # B1 and ## 10, 13, 25.
Problem Set B
- B1. Prove combinatorially the formula in Ch. 5, #19:
m2 = 2 (m choose 2) + (m choose 1).
- B2. Prove combinatorially that (n choose k) = (n choose n-k) for n ≥ k ≥ 0.
- B3. Write from memory a combinatorial proof of Pascal's Formula:
(n choose k) = (n-1 choose k) + (n-1 choose k-1) for n > k > 0.
(If you can't remember it, look it up in Ch. 2 and then reproduce it with the book closed.)
Then extend the combinatorial proof to cover all the cases where k, n ≥ 0. How do you handle these cases?
HOMEWORK VI (10/6)
Read for Wed., 10/7: Sects. 5.3-4.
Read for Fri., 10/9: Sects. 5.4-5 and Meshalkin's Theorem.
Do for discussion on
Fri., 10/9: Ch. 5, ## 14, 19, 22, and C1(a-h), C2. (In #14, don't assume k ≤ r.)
Mon., 10/12: Ch. 5, ## 17, 18, 20, and C1(i), C4. In #20, simplify your answer as far as you can.
Tues., 10/13: Ch. 5, ## 29, 30, 35, 37, 39, and C3.
Hand in Wed., 10/14: Ch. 5, ## 11, 21, 31, 44, and C1(j), C5.
(Warning: This is a long one; prepare days ahead.)
- Grading of # 31: 4+4: 4 for how convincing your proof is, 4 for how good your method or technique is.
- Grading of # C1(j): 4+4+(bonus 2): 4 for the values, 4 for an explicit general formula, 2 (bonus) for a proof.
- Grading of # C5: 4+4: 4 for formula and proof, 4 for series expansion.
Problem Set C
- C1. Evaluate (that means, as an actual number) the following binomial coefficients. Look for patterns. Simplify.
- (5 choose 4)
- (4 choose 5)
- (5.6 choose 2)
- (0 choose 0)
- (0 choose 7)
- (7 choose −1)
- (0 choose −1)
- (−1 choose r) for r = 0, 1, 2, 3, 4. Can you guess a general pattern for (−1 choose r) (no proof required)?
- (1/2 choose r) for r = 0, 1, 2, 3, 4. Can you guess a general pattern for (1/2 choose r) (no proof required)?
- (−1/2 choose r) for r = 0, 1, 2, 3, 4. Can you guess a general pattern for (−1/2 choose r) (no proof required)?
- C2. Give a combinatorial proof of formula (5.8). (Hints? The combinatorial proofs of #10 or #B1 or Pascal's formula might suggest an idea.)
- C3. Give a combinatorial proof of the first equation in Ch. 5, #7.
- C4. Find and prove a simple formula for (−1 choose n), n ≥ 0. Use your formula to find a simple power series expansion of 1/(1-x).
- C5. Find and prove a simple formula for (−2 choose n), n ≥ 0. Use your formula to find a simple power series expansion of 1/(1-x)2.
HOMEWORK VII (10/15)
Read for Fri., 10/16: Sect. 6.1.
Read for Mon., 10/17: Sects. 6.2-3.
Do for discussion on
Mon., 10/19: Ch. 6, ## 1, 3, 17.
Tues., 10/20: # D1; also Ch. 6, ## 4, 7, 11.
Wed., 10/21: Ch. 6, ## 10, 12.
Fri., 10/23: Ch. 6, ## 6, 15, 20, 21.
Hand in Fri., 10/23: # D2; also Ch. 6, ## 5, 8, 14, 16.
Problem Set D
Here are two simple problems in extremal set theory (which means problems like Sperner's Theorem, but they don't necessarily use Sperner's Theorem).
- D1. What is the largest number of combinations of an n-element set that can be chosen, so that any two chosen combinations have empty intersection?
- D2. What is the largest number of combinations of an n-element set that can be chosen, so that no two chosen combinations have empty intersection?
TEST II is on Tuesday, Oct. 27. It will cover Homework Sets V-VII. The grades should be in on Friday, Oct. 30.
HOMEWORK VIII (10/24)
Read for Fri., 10/30: Sect. 6.4.
Read for Mon., 11/2: Sect. 6.5.
Do for discussion on
Mon., 11/2: Ch. 6, ## 24(a), 25, 30, and ## E1, E2
Tues., 11/3: Ch. 6, ## 24(b), 27, 33, and ## E3, E4.
Hand in Wed., 11/4: Ch. 6, ## 21, 24(c), 28, 29.
Problem Set E
- E1. Find the number of solutions to x1 + x2 + x3 + x4 = 22 in integers that satisfy
x1 ≤ 14, x2 ≤ 14, x3 ≤ 14, x4 ≤ 7, and
- all xi ≥ 0;
- all xi > 0.
- E2. Find a formula for the number of r-combinations of the multiset
M = {infty·a1 , infty·a2 , 100·a3 , 100·a4},
for all integers r ≥ 0. ("infty" means infinity, as you probably suspected.)
- E3. Given integers a and b, 0 < a < b, how many numbers from a to b (inclusive) are not divisible by either 10 or 15? (See E5.)
- **E4. How many ways are there to place ceiling(n/2) nonattacking crooks (i.e., the maximum number) on an n × n triangular board? (Read about it.)
- E5. Given a positive integer k and integers a, b that satisfy 0 < a < b, how many numbers from a to b (inclusive) are divisible by k? (This is to help you with E3.)
HOMEWORK SET IX (10/24)
Read for Fri. 11/6: Section 3.1.
Do for discussion on
Mon. 11/9: Ch. 3, ## 1, 4, 5, 7.
Tues. 11/10: Ch. 3, ## 2, 3, 9, 16 (see remark).
Wed. 11/11: Ch. 3, ## 18, 26.
Hand in Fri. 11/13:
Ch. 3, ## 1 (for k = 23), 6, 11, 15, and # F1, F2.
Problem Set F
HOMEWORK SET X (11/13)
Read for Mon., 11/16: Section 3.2.
Do for discussion on:
Tues. 11/17: Ch. 3, ## 8, 13, 14, 28, and # G2.
Hand in Fri. 11/20: Ch. 3, ## 1 (for k = 23, 24), 17, 19, and # G1.
Problem Set G
- G1. Find a sequence of N numbers that has no increasing and no decreasing subsequence of length n + 1, where
- n = 3, N = 9;
- n = 4, N = 16;
- N = n2 for any n ≥ 1.
- G2. Concerning Application 9, here are some sequences of N = n2 + 1 numbers. For each sequence, find m1,
m2, ..., mN (defined in the book) and find a longest increasing subsequence. Then find a value m such that more than n different
mi's equal m, if such an m exists. If m exists, use it to find a decreasing subsequence longer than n. If no m exists, use the
mi's to find an increasing subsequence longer than n.
- n = 3, and the sequence is 3, -1, -π, π, 3.2, 1.88, 3, 0, 14, 7.
- n = 3, and the sequence is 5, 9, -2, 0, -1, -4, 55, 44, 22, 23.
- n = 3, and the sequence is 5, 9, -2, 55, -1, -4, 0, 44, 22, 23.
- G3. (A challenge problem.) In Ch. 3 #26, suppose we interpret the question to mean that the heights must be strictly increasing in every row before rearrangement, and strictly increasing in every column (and row) after rearrangement. This means that, before the rearrangement there must be no two equal heights in any row or column. However, that doesn't rule out having two equal heights that aren't in the same row or column. Problem. If there are equal heights (not in a row or column), is it always true that after rearrangement we still have no equal heights in any row, or, contrariwise, is there an example where, after rearrangement, some row may have equal heights? (As far as I know, this is a new problem. I certainly don't know the answer.) (A possible term project.)
HOMEWORK SET XI (11/17-19)
Read for Fri., 11/20: Sections 7.1-2.
Read for Mon., 11/23: Section 7.4 to the middle of p. 236.
Do for discussion on:
Tues. 11/24: Ch. 7, ## 1(a), 2, 4, 8, 13(a-c), 14(a-c), 17, 34.
Hand in by Wed. 11/25 before noon at my office or mailbox:
Ch. 7, ## 13(d), 14(d,e), 33 (using g.f.).
HOMEWORK SET XII (11/19-24,12/1)
Read for Mon., 11/30: Sections 7.4-6.
Do for discussion on:
Wed. 12/2: Ch. 7, ## 37, 46 (by g.f.), 48(e), 50, 52, 53.
Hand in either: Thurs. 12/3 (at my office or mailbox by 4:00), if you want them back on Friday, or: Fri. 12/4:
Ch. 7, ## 14(d)(find a formula for hn), 41 (& find initial condition; note that the diagonals here cannot meet at their endpoints), 48(c), 51.
TEST III is on Tuesday, Dec. 8. It will cover Homework Sets VIII-XII. The grades should be in on Friday, Dec. 11.
HOMEWORK SET XIII (12/1,6)
Read for Wed., 12/9:
Section 10.1: pp. 341-344 (omit the GCD algorithm pp. 344-346), Thm. 10.1.2 (omit proof), Cor. 10.1.3.
Section 10.4: pp. 368-374, Thm. 10.4.4 (omit example), pp. 376-377.
Do for discussion on:
Wed. 12/9: Ch. 10, ## 1, 3, 8, 13, 38, 42, 48.
Do for discussion on:
Fri. 12/11: Ch. 7, # 7 (optional challenge problem).
Hand in Fri. 12/11:
Ch. 10, # 41.
Go to rules for homework | announcements | course information | syllabus.